結果
問題 | No.1566 All Even |
ユーザー |
![]() |
提出日時 | 2021-04-13 21:33:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 3,430 bytes |
コンパイル時間 | 4,272 ms |
コンパイル使用メモリ | 254,108 KB |
最終ジャッジ日時 | 2025-01-20 17:11:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = long long;#define all(s) (s).begin(),(s).end()#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define se second#define P pair<ll,ll>#define REP(i, n) for (int i = 0; i < (n); ++i)const ll mod = 998244353;//const ll mod = 1000000007;const ll inf = 2000000000000000000ll;static const long double pi = 3.141592653589793;template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}void YesNo(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}void YESNO(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;}template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;}template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else returnvector(arg,make_vector<T>(x,args...));}ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }void gbjsmzmfuuvdf(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(20);}void solve(vector<vector<ll>> &ans){for(int i=1;i<ans.size();i++){for(int j=1;j<ans.size();j++){ans[i][j]=(ans[i][j-1]+ans[i-1][j]+ans[i-1][j-1])%2;}}}bool subsolve(vector<vector<ll>> ans){for(int i=2;i<=ans.size();i++){for(int x=0;x+i<ans.size();x++){for(int z=0;z+i<ans.size();z++){ll p=0;for(int a=x;a<=x+i;a++){for(int b=z;b<=z+i;b++){p+=ans[a][b];}}if(p%2==i%2){return false;}}}}return true;}int main() {gbjsmzmfuuvdf();ll n,m;cin>>n>>m;if(n==1){if(m){cout<<1<<endl;}else{cout<<2<<endl;}return 0;}if(n>=7){bool t=true;while(m--){ll a,b,c;cin>>a>>b>>c;a--;b--;if(c==0){t=false;}}if(t){cout<<1<<endl;}else{cout<<0<<endl;return 0;}}if(n<=6){vector<ll> x(m),y(m),z(m);for(int i=0;i<m;i++){cin>>x[i]>>y[i]>>z[i];x[i]--;y[i]--;}ll count=0;for(int i=0;i<(1<<(2*n-1));i++){vector<vector<ll>> ans(n,vector<ll>(n));ll k=i;for(int j=0;j<n;j++){ans[j][0]=k%2;k/=2;}for(int j=1;j<n;j++){ans[0][j]=k%2;k/=2;}solve(ans);bool check=true;for(int j=0;j<m;j++){if(ans[x[j]][y[j]]!=z[j]){check=false;}}if(check&&subsolve(ans)){count++;}}cout<<count<<endl;}}