超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC018C解いてみた

見てもわからず、答えを見て実装してみました。
なお、この手のx_i=(x_{i-1} + a) % pの漸化式による、乱数生成法を線形合同法と呼びます。

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <utility>
#include <algorithm>

#define AT(x,y) ((x) * M + y)

using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> PP;

PP G[1000*1000+10];
vector<PP> sortedG[1000+10];

int main() {
  int N,M;
  int x_0,a,p;

  scanf("%d%d", &N,&M);
  scanf("%d%d%d", &x_0, &a, &p);

  for(int i=0;i<N;++i) {
    for(int j=0;j<M;++j) {
      if(i==0 && j==0) {
        G[AT(i,j)] = PP(x_0, P(i,j));
      } else if(j==0) {
        G[AT(i,j)] = PP((G[AT(i-1,M-1)].first + a) % p,P(i,j));
      } else {
        G[AT(i,j)] = PP((G[AT(i,j-1)].first + a) % p, P(i,j));
      }
      //printf("%d ", G[AT(i,j)].first);
    }
    //printf("\n");
  }

  sort(G, G+(N*M));

  int work = 0;

  for(int i=0;i<N;++i) {
    for(int j=0;j<M;++j) {
      sortedG[i].push_back(PP(G[AT(i,j)].second.second, G[AT(i,j)].second));
    }
    sort(sortedG[i].begin(), sortedG[i].end());

    for(int j=0;j<M;++j) {
      work += abs(sortedG[i][j].second.second - j) + abs(sortedG[i][j].second.first - i);
    }
  }

  printf("%d\n", work);


  return 0;
}