結果

問題 No.2824 Lights Up! (Grid Edition)
コンテスト
ユーザー hos.lyric
提出日時 2024-07-27 00:00:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 4,170 bytes
コンパイル時間 1,248 ms
コンパイル使用メモリ 118,080 KB
実行使用メモリ 16,600 KB
最終ジャッジ日時 2024-07-27 00:00:40
合計ジャッジ時間 8,158 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


void exper() {
  for (int N = 1; N <= 5; ++N) {
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
      vector<vector<int>> a(N, vector<int>(N, 0));
      auto oper = [&](int i, int j) -> void {
        a[i][j] ^= 1;
        a[(i + N - 1) % N][j] ^= 1;
        a[i][(j + N - 1) % N] ^= 1;
        a[(i + N - 1) % N][(j + N - 1) % N] ^= 1;
      };
      oper(x, y);
      oper(x, 0);
      oper(0, y);
      vector<vector<int>> b(N + 1, vector<int>(N + 1, 0));
      for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        b[i + 1][j + 1] = b[i + 1][j] ^ b[i][j + 1] ^ b[i][j] ^ a[i][j];
      }
      cerr << N << " " << x << " " << y << endl;
      for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) cerr << ".#"[b[i][j]];
        cerr << endl;
      }
    }
  }
}


int N;
char S[1010][1010];
int T[1010][1010];
int t[1010][1010];
int ans[1010][1010];

bool solve() {
  memset(T, 0, sizeof(T));
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
    T[x + 1][y + 1] = T[x + 1][y] ^ T[x][y + 1] ^ T[x][y] ^ ((S[x][y] != '.') ? 1 : 0);
  }
  for (int x = 0; x <= N; ++x) for (int y = 0; y <= N; ++y) if (x == 0 || x == N || y == 0 || y == N) {
    if (T[x][y]) return false;
  }
#ifdef LOCAL
for(int x=0;x<=N;++x){for(int y=0;y<=N;++y)cerr<<".#"[T[x][y]];cerr<<endl;}
#endif
  
  if (N >= 2) {
    if ((N - 1) & 1) {
      for (int a = 0; a < 2; ++a) {
        memcpy(t, T, sizeof(T));
        memset(ans, 0, sizeof(ans));
        for (int x = 1; x < N; ++x) for (int y = 0; y < N; ++y) t[x][y] ^= a;
        ans[0][0] ^= a;
        for (int x = 2; x < N; ++x) for (int y = 2; y < N; ++y) if (t[x][y]) {
          t[1][1] ^= 1;
          t[1][y] ^= 1;
          t[x][1] ^= 1;
          t[x][y] ^= 1;
          ans[1][1] ^= 1;
          ans[1][y] ^= 1;
          ans[x][1] ^= 1;
          ans[x][y] ^= 1;
        }
        bool ok = true;
        for (int x = 1; x < N; ++x) for (int y = 1; y < N; ++y) ok = ok && (!t[x][y]);
        if (ok) {
// cerr<<"ok a = "<<a<<endl;
          goto found;
        }
      }
      return false;
     found:{}
    } else {
      vector<int> row(N, 0), col(N, 0);
      memset(ans, 0, sizeof(ans));
      for (int x = 1; x < N; ++x) for (int y = 1; y < N; ++y) if (T[x][y]) {
        ans[x][y] ^= 1;
        row[x] ^= 1;
        col[y] ^= 1;
      }
      for (int x = 1; x < N; ++x) for (int y = 1; y < N; ++y) {
        ans[x][y] ^= row[x];
        ans[x][y] ^= col[y];
      }
    }
  }
  
  int ansCnt = 0;
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) if (ans[x][y]) ++ansCnt;
  printf("%d\n", ansCnt);
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) if (ans[x][y]) printf("%d %d\n", x, y);
  return true;
}

int main() {
  // exper();
  
  for (; ~scanf("%d", &N); ) {
    for (int x = 0; x < N; ++x) {
      scanf("%s", S[x]);
    }
    
    const bool res = solve();
    if (!res) {
      puts("-1");
    }
  }
  return 0;
}
0