結果
問題 | No.1566 All Even |
ユーザー |
![]() |
提出日時 | 2021-06-26 14:35:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 3,740 bytes |
コンパイル時間 | 3,592 ms |
コンパイル使用メモリ | 257,484 KB |
最終ジャッジ日時 | 2025-01-22 13:25:29 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;#define rep(i,n)for (int i = 0; i < int(n); ++i)#define rrep(i,n)for (int i = int(n)-1; i >= 0; --i)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()template<class T> void chmax(T& a, const T& b) {a = max(a, b);}template<class T> void chmin(T& a, const T& b) {a = min(a, b);}using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;int case_5[8][5][5] = {{{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},{1, 1, 1, 1, 1},{0, 0, 0, 0, 0},{0, 0, 0, 0, 0},},{{0, 0, 1, 0, 0},{0, 0, 1, 0, 0},{0, 0, 1, 0, 0},{0, 0, 1, 0, 0},{0, 0, 1, 0, 0},},{{0, 1, 1, 0, 1},{1, 0, 0, 1, 0},{0, 1, 1, 0, 1},{0, 1, 1, 0, 1},{1, 0, 0, 1, 0},},{{0, 1, 0, 0, 1},{1, 0, 1, 1, 0},{1, 0, 1, 1, 0},{0, 1, 0, 0, 1},{1, 0, 1, 1, 0},},{{1, 0, 1, 1, 0},{0, 1, 0, 0, 1},{1, 0, 1, 1, 0},{1, 0, 1, 1, 0},{0, 1, 0, 0, 1},},{{1, 0, 0, 1, 0},{0, 1, 1, 0, 1},{0, 1, 1, 0, 1},{1, 0, 0, 1, 0},{0, 1, 1, 0, 1},},{{1, 1, 0, 1, 1},{1, 1, 0, 1, 1},{0, 0, 1, 0, 0},{1, 1, 0, 1, 1},{1, 1, 0, 1, 1},},{{1, 1, 1, 1, 1},{1, 1, 1, 1, 1},{1, 1, 1, 1, 1},{1, 1, 1, 1, 1},{1, 1, 1, 1, 1},}};int case_6[2][6][6] = {{{1, 0, 1, 1, 0, 1},{0, 1, 0, 0, 1, 0},{1, 0, 1, 1, 0, 1},{1, 0, 1, 1, 0, 1},{0, 1, 0, 0, 1, 0},{1, 0, 1, 1, 0, 1},},{{1, 1, 1, 1, 1, 1},{1, 1, 1, 1, 1, 1},{1, 1, 1, 1, 1, 1},{1, 1, 1, 1, 1, 1},{1, 1, 1, 1, 1, 1},{1, 1, 1, 1, 1, 1},}};bool g[11][11];bool s[11][11];int m;vector<tuple<int, int, int>> xyz;int solve5() {int ans = 0;rep(i, 8) {bool ok = true;for(auto [x, y, z]: xyz) {if (case_5[i][x][y] != z) {ok = false;break;}}ans += ok;}cout << ans << endl;return 0;}int solve6() {int ans = 0;rep(i, 2) {bool ok = true;for(auto [x, y, z]: xyz) {if (case_6[i][x][y] != z) {ok = false;break;}}ans += ok;}cout << ans << endl;return 0;}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;cin >> m;xyz.resize(m);rep(i, m) {int x, y, z;cin >> x >> y >> z;x--, y--;xyz[i] = {x, y, z};}if (n == 5) return solve5();if (n < 5) {int ans = 0;rep(bit, 1 << n * n) {int t = bit;rep(i, n) rep(j, n) g[i][j] = t & 1, t >>= 1;bool ok = true;rep(i, n) rep(j, n) s[i+1][j+1] = s[i+1][j] ^ s[i][j+1] ^ s[i][j] ^ g[i][j];rep(i, n) rep(j, n) for(int k = 2; i + k <= n && j + k <= n; k++) {if ((s[i][j] ^ s[i + k][j] ^ s[i][j + k] ^ s[i+k][j+k] ^ k) & 1) {ok = false;goto done;}}done:if (!ok) continue;// rep(i, n) rep(j, n) cout << int(g[i][j]) << " \n"[j + 1 == n];// cout << endl;for(auto [x, y, z]: xyz) {if (g[x][y] != z) {ok = false;break;}}ans += ok;}cout << ans << '\n';return 0;} else if (n == 6) {return solve6();}bool ok = true;for(auto [x, y, z]: xyz) {if (z != 1) {ok = false;break;}}cout << int(ok) << '\n';}