結果

問題 No.5002 stick xor
コンテスト
ユーザー 0x19f
提出日時 2018-05-29 06:50:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 991 ms / 1,000 ms
コード長 2,410 bytes
コンパイル時間 35,763 ms
実行使用メモリ 1,552 KB
スコア 39,959
最終ジャッジ日時 2018-05-29 06:51:12
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
using namespace std;

const int INF = 1 << 28;
vector<int> dy = { -1, +1, +0, +0 };
vector<int> dx = { +0, +0, -1, +1 };

int eval(vector< vector<int> > &A, int N, int i, int j) {
  int w = 0;
  REP(k, 0, 4) {
    int y = i + dy[k];
    int x = j + dx[k];
    if(0 <= y && y < N && 0 <= x && x < N) {
      if(A[i][j] == A[y][x]) w++;
    }
  }
  return w;
}

int main(void) {
  int N, K;
  cin >> N >> K;
  vector<int> L(K);
  REP(i, 0, K) cin >> L[i];
  vector< vector<int> > A(N, vector<int>(N));
  REP(i, 0, N) REP(j, 0, N) {
    char c;
    cin >> c;
    A[i][j] = c - '0';
  }

  int init = 0;
  REP(i, 0, N) REP(j, 0, N) if(A[i][j] == 0) init++;

  vector<int> lx(K), ly(K), rx(K), ry(K);
  REP(i, 0, K) {
    int maxw = -INF, maxt, maxy, maxx;

    REP(y, 0, N - L[i]) REP(x, 0, N) {
      int w = 0;
      if(L[i] <= 25) {
        REP(k, y, y + L[i]) A[k][x] = !A[k][x];
        REP(k, y, y + L[i]) w += eval(A, N, k, x);
        REP(k, y, y + L[i]) A[k][x] = !A[k][x];
      }
      REP(k, y, y + L[i]) {
        if(A[k][x] == 0) w--;
        if(A[k][x] == 1) w++;
      }
      if(w > maxw) {
        maxw = w;
        maxt = 0;
        maxy = y;
        maxx = x;
      }
    }

    REP(y, 0, N) REP(x, 0, N - L[i]) {
      int w = 0;
      if(L[i] <= 25) {
        REP(k, x, x + L[i]) A[y][k] = !A[y][k];
        REP(k, x, x + L[i]) w += eval(A, N, y, k);
        REP(k, x, x + L[i]) A[y][k] = !A[y][k];
      }
      REP(k, x, x + L[i]) {
        if(A[y][k] == 0) w--;
        if(A[y][k] == 1) w++;
      }
      if(w > maxw) {
        maxw = w;
        maxt = 1;
        maxy = y;
        maxx = x;
      }
    }

    if(maxt == 0) {
      ly[i] = maxy + 1;
      lx[i] = maxx + 1;
      ry[i] = maxy + L[i];
      rx[i] = maxx + 1;
      REP(k, maxy, maxy + L[i]) A[k][maxx] = !A[k][maxx];
    }
    if(maxt == 1) {
      ly[i] = maxy + 1;
      lx[i] = maxx + 1;
      ry[i] = maxy + 1;
      rx[i] = maxx + L[i];
      REP(k, maxx, maxx + L[i]) A[maxy][k] = !A[maxy][k];
    }
  }

  REP(i, 0, K) cout << ly[i] << " " << lx[i] << " " << ry[i] << " " << rx[i] << endl;

#ifdef LOCAL
  int score = 0;
  REP(i, 0, N) REP(j, 0, N) if(A[i][j] == 0) score++;
  score -= init;

  cerr << "score: " << score << endl;
  // REP(i, 0, N) {
  //   REP(j, 0, N) cerr << A[i][j];
  //   cerr << endl;
  // }
#endif
}
0