#998000 (C++14) No.2824 Lights Up! (Grid Edition)

提出ソース

結果

問題	No.2824 Lights Up! (Grid Edition)
ユーザー	hos.lyric
提出日時	2024-07-27 00:00:30
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 13,568 KB
testcase_01	AC	5 ms 13,568 KB
testcase_02	AC	6 ms 15,488 KB
testcase_03	AC	3 ms 8,024 KB
testcase_04	AC	8 ms 9,724 KB
testcase_05	AC	34 ms 16,596 KB
testcase_06	AC	8 ms 9,132 KB
testcase_07	AC	99 ms 16,600 KB
testcase_08	AC	9 ms 8,752 KB
testcase_09	AC	29 ms 16,472 KB
testcase_10	AC	8 ms 9,132 KB
testcase_11	AC	92 ms 16,600 KB
testcase_12	AC	8 ms 8,880 KB
testcase_13	AC	88 ms 14,432 KB
testcase_14	AC	8 ms 9,004 KB
testcase_15	AC	102 ms 14,560 KB
testcase_16	AC	8 ms 8,624 KB
testcase_17	AC	91 ms 14,556 KB
testcase_18	AC	8 ms 9,260 KB
testcase_19	AC	118 ms 14,556 KB
testcase_20	AC	5 ms 9,088 KB
testcase_21	AC	22 ms 16,300 KB
testcase_22	AC	3 ms 7,780 KB
testcase_23	AC	75 ms 16,512 KB
testcase_24	AC	4 ms 13,796 KB
testcase_25	AC	8 ms 13,748 KB
testcase_26	AC	5 ms 9,824 KB
testcase_27	AC	67 ms 14,400 KB
testcase_28	AC	3 ms 7,652 KB
testcase_29	AC	11 ms 13,972 KB
testcase_30	AC	3 ms 9,656 KB
testcase_31	AC	4 ms 14,060 KB
testcase_32	AC	4 ms 9,548 KB
testcase_33	AC	8 ms 15,488 KB
testcase_34	AC	3 ms 7,824 KB
testcase_35	AC	5 ms 13,592 KB
testcase_36	AC	3 ms 8,024 KB
testcase_37	AC	4 ms 14,112 KB
testcase_38	AC	3 ms 7,756 KB
testcase_39	AC	6 ms 15,764 KB
testcase_40	AC	3 ms 8,292 KB
testcase_41	AC	7 ms 15,492 KB
testcase_42	AC	3 ms 8,412 KB
testcase_43	AC	5 ms 13,452 KB
testcase_44	AC	3 ms 8,016 KB
testcase_45	AC	3 ms 8,148 KB
testcase_46	AC	6 ms 15,492 KB
testcase_47	AC	5 ms 13,572 KB
testcase_48	AC	6 ms 15,952 KB
testcase_49	AC	6 ms 15,612 KB
testcase_50	AC	3 ms 8,148 KB
testcase_51	AC	5 ms 15,484 KB
testcase_52	AC	4 ms 13,572 KB
testcase_53	AC	4 ms 14,056 KB
testcase_54	AC	3 ms 8,404 KB
testcase_55	AC	6 ms 13,440 KB
testcase_56	AC	3 ms 7,896 KB
testcase_57	AC	6 ms 15,732 KB
testcase_58	AC	3 ms 8,024 KB
testcase_59	AC	6 ms 15,744 KB
testcase_60	AC	3 ms 8,660 KB
testcase_61	AC	6 ms 13,696 KB
testcase_62	AC	3 ms 9,680 KB
testcase_63	AC	5 ms 13,568 KB
testcase_64	AC	3 ms 7,768 KB
testcase_65	AC	6 ms 16,068 KB
testcase_66	AC	3 ms 8,024 KB
testcase_67	AC	6 ms 16,076 KB
testcase_68	AC	5 ms 15,616 KB
testcase_69	AC	2 ms 7,632 KB
testcase_70	AC	3 ms 9,680 KB
testcase_71	AC	3 ms 7,884 KB
testcase_72	AC	3 ms 8,652 KB
testcase_73	AC	4 ms 8,272 KB
testcase_74	AC	2 ms 7,632 KB
testcase_75	AC	3 ms 8,532 KB
testcase_76	AC	3 ms 9,676 KB
testcase_77	AC	4 ms 7,892 KB
testcase_78	AC	3 ms 7,756 KB
testcase_79	AC	3 ms 7,504 KB
testcase_80	AC	3 ms 9,676 KB
testcase_81	AC	3 ms 7,756 KB
testcase_82	AC	3 ms 7,756 KB
testcase_83	AC	6 ms 15,488 KB
testcase_84	AC	4 ms 13,572 KB
testcase_85	AC	5 ms 13,568 KB
testcase_86	AC	5 ms 13,700 KB
testcase_87	AC	5 ms 13,436 KB
testcase_88	AC	3 ms 8,400 KB
testcase_89	AC	3 ms 8,528 KB
testcase_90	AC	5 ms 13,440 KB
testcase_91	AC	6 ms 13,696 KB
testcase_92	AC	5 ms 13,564 KB
testcase_93	AC	4 ms 14,260 KB
testcase_94	AC	3 ms 7,756 KB
testcase_95	AC	5 ms 13,572 KB
testcase_96	AC	5 ms 14,224 KB
testcase_97	AC	6 ms 14,808 KB
testcase_98	AC	5 ms 13,696 KB
testcase_99	AC	5 ms 13,892 KB
testcase_100	AC	5 ms 13,568 KB
testcase_101	AC	4 ms 13,572 KB
testcase_102	AC	7 ms 13,696 KB
testcase_103	AC	4 ms 9,672 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード