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

提出ソース

結果

問題	No.2824 Lights Up! (Grid Edition)
ユーザー	hos.lyric
提出日時	2024-07-26 23:49:04
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,063 bytes
コンパイル時間	1,436 ms
コンパイル使用メモリ	117,288 KB
実行使用メモリ	16,604 KB
最終ジャッジ日時	2024-07-26 23:49:12
合計ジャッジ時間	8,543 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	AC	5 ms 15,616 KB
testcase_03	AC	3 ms 7,892 KB
testcase_04	AC	9 ms 8,744 KB
testcase_05	AC	28 ms 16,600 KB
testcase_06	AC	8 ms 9,516 KB
testcase_07	WA	-
testcase_08	AC	9 ms 8,748 KB
testcase_09	AC	27 ms 16,472 KB
testcase_10	AC	8 ms 8,740 KB
testcase_11	AC	93 ms 16,604 KB
testcase_12	AC	8 ms 10,140 KB
testcase_13	WA	-
testcase_14	AC	9 ms 8,876 KB
testcase_15	WA	-
testcase_16	AC	9 ms 8,752 KB
testcase_17	WA	-
testcase_18	AC	9 ms 9,132 KB
testcase_19	WA	-
testcase_20	AC	5 ms 8,256 KB
testcase_21	AC	21 ms 16,424 KB
testcase_22	AC	3 ms 8,164 KB
testcase_23	AC	77 ms 16,536 KB
testcase_24	AC	5 ms 13,668 KB
testcase_25	WA	-
testcase_26	AC	5 ms 8,856 KB
testcase_27	WA	-
testcase_28	AC	3 ms 8,524 KB
testcase_29	WA	-
testcase_30	AC	4 ms 8,752 KB
testcase_31	WA	-
testcase_32	AC	4 ms 8,048 KB
testcase_33	AC	8 ms 15,612 KB
testcase_34	AC	3 ms 8,340 KB
testcase_35	WA	-
testcase_36	AC	4 ms 7,896 KB
testcase_37	WA	-
testcase_38	AC	3 ms 8,572 KB
testcase_39	AC	6 ms 15,760 KB
testcase_40	AC	3 ms 8,680 KB
testcase_41	AC	7 ms 15,620 KB
testcase_42	AC	3 ms 8,156 KB
testcase_43	WA	-
testcase_44	AC	3 ms 8,148 KB
testcase_45	AC	3 ms 9,808 KB
testcase_46	AC	7 ms 15,488 KB
testcase_47	AC	5 ms 13,700 KB
testcase_48	AC	6 ms 15,740 KB
testcase_49	WA	-
testcase_50	AC	3 ms 8,140 KB
testcase_51	AC	6 ms 15,608 KB
testcase_52	AC	5 ms 13,696 KB
testcase_53	AC	5 ms 13,696 KB
testcase_54	AC	3 ms 8,148 KB
testcase_55	WA	-
testcase_56	AC	4 ms 8,276 KB
testcase_57	AC	7 ms 15,616 KB
testcase_58	AC	3 ms 7,756 KB
testcase_59	AC	6 ms 15,740 KB
testcase_60	AC	3 ms 7,756 KB
testcase_61	WA	-
testcase_62	AC	3 ms 8,020 KB
testcase_63	WA	-
testcase_64	AC	3 ms 8,276 KB
testcase_65	AC	7 ms 15,616 KB
testcase_66	AC	3 ms 8,660 KB
testcase_67	AC	5 ms 15,744 KB
testcase_68	AC	6 ms 15,612 KB
testcase_69	AC	3 ms 7,756 KB
testcase_70	AC	3 ms 8,524 KB
testcase_71	AC	3 ms 8,016 KB
testcase_72	AC	3 ms 9,808 KB
testcase_73	AC	3 ms 9,808 KB
testcase_74	AC	4 ms 8,404 KB
testcase_75	AC	3 ms 7,888 KB
testcase_76	AC	3 ms 8,784 KB
testcase_77	AC	4 ms 8,656 KB
testcase_78	AC	3 ms 8,528 KB
testcase_79	AC	3 ms 7,892 KB
testcase_80	AC	3 ms 7,888 KB
testcase_81	AC	3 ms 7,888 KB
testcase_82	AC	3 ms 9,804 KB
testcase_83	WA	-
testcase_84	AC	4 ms 14,220 KB
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	AC	3 ms 8,536 KB
testcase_89	AC	3 ms 7,892 KB
testcase_90	WA	-
testcase_91	WA	-
testcase_92	AC	4 ms 13,564 KB
testcase_93	WA	-
testcase_94	AC	3 ms 8,404 KB
testcase_95	AC	5 ms 13,700 KB
testcase_96	WA	-
testcase_97	WA	-
testcase_98	WA	-
testcase_99	WA	-
testcase_100	WA	-
testcase_101	AC	5 ms 13,564 KB
testcase_102	WA	-
testcase_103	AC	3 ms 9,800 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));
        ans[0][0] ^= a;
        for (int x = 2; x < N; ++x) for (int y = 2; y < N; ++y) if (t[x][y] ^ a) {
          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) {
          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 (T[x][y]) ++ansCnt;
  printf("%d\n", ansCnt);
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) if (T[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

結果

テストケース

ソースコード