#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=1005; int n,m,a[N],b[N],vis[N]; void BellaKira() { cin>>n>>m; for (int i=1;i<=m;i++) { cin>>a[i]>>b[i],a[i]--,b[i]--; assert(a[i]!=b[i]); assert(a[i]<n); assert(b[i]<n); } for (int len=1;len<=n;len++) { poly G; for (int i=0;i+len-1<n;i++) { int now=0; for (int j=i;j<=i+len-1;j++) now|=(1ll<<j); G.push_back(now); } for (int i=m;i>=1;i--) { poly ers; for (auto u:G) { int x=a[i],y=b[i]; if (((u>>x)&1)==0&&((u>>y)&1)==1) { // ers.push_back(u); ers.push_back(u^(1ll<<x)^(1ll<<y)); } else if (!(((u>>x)^(u>>y))&1)) { // ers.push_back(u); } else { ers.push_back(u); } } sort(ers.begin(),ers.end()); int j=0; poly nxt; for (auto u:G) { while (j<sz(ers)&&ers[j]<u) { if (nxt.size()&&ers[j]==nxt.back()) nxt.pop_back(); else nxt.push_back(ers[j]); j++; } if (nxt.size()&&u==nxt.back()) nxt.pop_back(); else nxt.push_back(u); } while (j<sz(ers)) { if (nxt.size()&&ers[j]==nxt.back()) nxt.pop_back(); else nxt.push_back(ers[j]); j++; } nxt.swap(G); if (G.empty()) break; // for (int j=1;j<sz(G);j++) // assert(G[j]>G[j-1]); // cerr<<sz(G)<<endl; } cout<<(sz(G)&1)<<' '; } cout<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=1005; int n,m,a[N],b[N],vis[N]; void BellaKira() { cin>>n>>m; for (int i=1;i<=m;i++) { cin>>a[i]>>b[i],a[i]--,b[i]--; assert(a[i]!=b[i]); assert(a[i]<n); assert(b[i]<n); } for (int len=1;len<=n;len++) { poly G; for (int i=0;i+len-1<n;i++) { int now=0; for (int j=i;j<=i+len-1;j++) now|=(1ll<<j); G.push_back(now); } for (int i=m;i>=1;i--) { poly ers; for (auto u:G) { int x=a[i],y=b[i]; if (((u>>x)&1)==0&&((u>>y)&1)==1) { // ers.push_back(u); ers.push_back(u^(1ll<<x)^(1ll<<y)); } else if (!(((u>>x)^(u>>y))&1)) { // ers.push_back(u); } else { ers.push_back(u); } } sort(ers.begin(),ers.end()); int j=0; poly nxt; for (auto u:G) { while (j<sz(ers)&&ers[j]<u) { if (nxt.size()&&ers[j]==nxt.back()) nxt.pop_back(); else nxt.push_back(ers[j]); j++; } if (nxt.size()&&u==nxt.back()) nxt.pop_back(); else nxt.push_back(u); } while (j<sz(ers)) { if (nxt.size()&&ers[j]==nxt.back()) nxt.pop_back(); else nxt.push_back(ers[j]); j++; } nxt.swap(G); if (G.empty()) break; // for (int j=1;j<sz(G);j++) // assert(G[j]>G[j-1]); // cerr<<sz(G)<<endl; } cout<<(sz(G)&1)<<' '; } cout<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } } |