結果

問題 No.1056 2D Lamps
ユーザー 👑 hos.lyric
提出日時 2020-05-15 22:13:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 574 ms / 3,000 ms
コード長 3,716 bytes
コンパイル時間 1,708 ms
コンパイル使用メモリ 128,896 KB
最終ジャッジ日時 2025-01-10 11:42:35
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         scanf("%s", A[i][x]);
      |         ~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/bits/specfun.h:43,
                 from /usr/include/c++/13/cmath:3699,
                 from main.cpp:2:
In function ‘typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]’,
    inlined from ‘void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = int*; _Tp = int]’ at /usr/include/c++/13/bits/stl_algobase.h:977:21,
    inlined from ‘void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]’ at /usr/include/c++/13/bits/stl_algobase.h:1007:20,
    inlined from ‘int main()’ at main.cpp:137:9:
/usr/include/c++/13/bits/stl_algobase.h:931:18: warning: ‘void* __builtin_memset(void*, int, long unsigned int)’ specified bound between 18446744065119617024 and 18446744073709551612 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
  931 |         *__first = __tmp;
      |         ~~~~~~~~~^~~~~~~

ソースコード

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