Submission #883784

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class C_change_seats {
public:
    void solve(void) {
        int N,M;
        cin>>N>>M;

        ll x0,a,p;
        cin>>x0>>a>>p;

        if ( a % p == 0 )
        {
            if ( x0 < p )
                cout<<0<<endl;
            else  // table[0][0] のみ x0, 残りは x0%p になるケース
                cout<<(N-1)*2<<endl;// table[0][0] と table[n-1][0] を交換
            return;
        }

        vector<vector<ll>> table(N,vector<ll>(M));
        vector<vector<tuple<int,int>>> G(N);
        vector<ll> xs(N*M);

        ll  k = 0;
        ll  x = 0;
        REP(i,N)
        REP(j,M)
        {
            if (k == 0)
                x = table[i][j] = x0;
            else
                x = table[i][j] = (x+a)%p;
            xs[k++] = x;
        }
        sort(RANGE(xs));
        map<ll,ll> x2n;


        // O(N*M*log(N*M))
        // 成績を 0...N*M-1 までの連番にしておく
        // p が素数かつ N*M <= p なのでおなじ成績は存在しない
        k = 0;
        for (auto x : xs)
            x2n[x] = k++;

        // G[i][*]<G[j][*] の条件から
        // i 行目にいるべきは i==x/M なる x
        REP(i,N)
        REP(j,M)
            G[x2n[table[i][j]]/M].emplace_back(j,i);

        // おなじ行内部では入力順を保つような順番が最適のはず
        REP(i,N)
        {
            assert((int)G[i].size()==M);
            sort(RANGE(G[i]));
        }
        ll ret = 0;
        REP(i,N)
        REP(j,M)
        {
            int k,l;
            tie(l,k) = G[i][j];
            ret += abs(k-i)+abs(l-j);
        }
        cout<<ret<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new C_change_seats();
        obj->solve();
        delete obj;
        return 0;
}
#endif

Submission Info

Judge Result