結果

問題 No.1056 2D Lamps
コンテスト
ユーザー hos.lyric
提出日時 2020-05-15 22:16:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 621 ms / 3,000 ms
コード長 3,716 bytes
コンパイル時間 1,267 ms
コンパイル使用メモリ 113,708 KB
実行使用メモリ 18,432 KB
最終ジャッジ日時 2024-09-19 11:03:48
合計ジャッジ時間 6,461 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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 <map>
#include <numeric>
#include <queue>
#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> 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; }

constexpr int MAX_N = 200;
constexpr int MAX_M = 200;

int uf[MAX_M];
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}

int N, M;
char A[MAX_M][MAX_N][MAX_N + 1];

int esLen;
bitset<MAX_N * MAX_N> es[6 * MAX_N];
int fs[6 * MAX_N];

pair<vector<bool>, int> ps[MAX_M];

int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    for (int i = 0; i < M; ++i) {
      for (int x = 0; x < N; ++x) {
        scanf("%s", A[i][x]);
      }
    }
    
    esLen = 0;
    for (int x = 0; x < N; ++x) {
      es[esLen].reset();
      for (int y = 0; y < N; ++y) {
        es[esLen][x * N + y] = true;
      }
      ++esLen;
    }
    for (int y = 0; y < N; ++y) {
      es[esLen].reset();
      for (int x = 0; x < N; ++x) {
        es[esLen][x * N + y] = true;
      }
      ++esLen;
    }
    for (int k = 0; k <= 2 * N - 2; ++k) {
      es[esLen].reset();
      for (int x = 0; x < N; ++x) {
        const int y = k - x;
        if (0 <= y && y < N) {
          es[esLen][x * N + y] = true;
        }
      }
      ++esLen;
    }
    for (int k = -(N - 1); k <= N - 1; ++k) {
      es[esLen].reset();
      for (int x = 0; x < N; ++x) {
        const int y = x - k;
        if (0 <= y && y < N) {
          es[esLen][x * N + y] = true;
        }
      }
      ++esLen;
    }
// for(int j=0;j<esLen;++j){for(int z=0;z<N*N;++z){cerr<<es[j][z];}cerr<<endl;}cerr<<"----"<<endl;
    
    for (int j = 0; j < esLen; ++j) {
      for (int k = 0; k < j; ++k) {
        if (fs[k] != -1 && es[j][fs[k]]) {
          es[j] ^= es[k];
        }
      }
      fs[j] = es[j]._Find_first();
      if (fs[j] == MAX_N * MAX_N) {
        fs[j] = -1;
      }
    }
// for(int j=0;j<esLen;++j){for(int z=0;z<N*N;++z){cerr<<es[j][z];}cerr<<endl;}cerr<<"----"<<endl;
// cerr<<"fs = ";pv(fs,fs+esLen);
    
    for (int i = 0; i < M; ++i) {
      ps[i].second = i;
      bitset<MAX_N * MAX_N> b;
      for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
        if (A[i][x][y] == '#') {
          b[x * N + y] = true;
        }
      }
      for (int j = 0; j < esLen; ++j) {
        if (fs[j] != -1 && b[fs[j]]) {
          b ^= es[j];
        }
      }
      ps[i].first.resize(N * N);
      for (int z = 0; z < N * N; ++z) {
        ps[i].first[z] = b[z];
      }
    }
    sort(ps, ps + M);
    fill(uf, uf + M, -1);
    for (int i = 0; i < M - 1; ++i) {
      if (ps[i].first == ps[i + 1].first) {
        connect(ps[i].second, ps[i + 1].second);
      }
    }
    for (int i = 0; i < M - 1; ++i) {
      for (int j = i + 1; j < M; ++j) {
        putchar((root(i) == root(j)) ? '1' : '0');
      }
      puts("");
    }
  }
  return 0;
}
0