#include <bits/stdc++.h> using namespace std; int n, m; vector<pair<int,int>> v; set<long long> wybr; bool getBit(long long l, int b) { return ((l & (1<<b)) >> b); } void dzial(long long cur, int ruch) { if(ruch >= m) { wybr.insert(cur); return; } pair<int,int> r = v[m-ruch-1]; bool ba = getBit(cur,r.first), bb = getBit(cur,r.second); if( ba && !bb) return; //zle dzial(cur, ruch+1); if(ba == bb) return; //nie wystapil ruch cur = cur | (1<<r.first); cur = cur ^ (1<<r.second); dzial(cur, ruch+1); } int ileDla(int x) { wybr = set<long long>(); if(x==1) return n; if(x==n) return 1; long long cur = (1<<x)-1; dzial(cur,0); for (int i = x; i < n; ++i) { cur = cur | (1<<i); cur = cur ^ (1<<(i-x)); dzial(cur,0); } return wybr.size(); } int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); cin>> n >> m; v = vector<pair<int,int>>(m); int a,b; for(int i=0;i<m;i++){ cin >> a >> b; v[i] = {a-1,b-1}; } for (int i = 1; i <= n; ++i) { int w = ileDla(i); cout<<(w%2)<<" "; } //int w = ileDla(3); } /* 10 4 4 1 1 2 3 4 1 4 4 4 4 1 1 2 3 4 1 4 */
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 | #include <bits/stdc++.h> using namespace std; int n, m; vector<pair<int,int>> v; set<long long> wybr; bool getBit(long long l, int b) { return ((l & (1<<b)) >> b); } void dzial(long long cur, int ruch) { if(ruch >= m) { wybr.insert(cur); return; } pair<int,int> r = v[m-ruch-1]; bool ba = getBit(cur,r.first), bb = getBit(cur,r.second); if( ba && !bb) return; //zle dzial(cur, ruch+1); if(ba == bb) return; //nie wystapil ruch cur = cur | (1<<r.first); cur = cur ^ (1<<r.second); dzial(cur, ruch+1); } int ileDla(int x) { wybr = set<long long>(); if(x==1) return n; if(x==n) return 1; long long cur = (1<<x)-1; dzial(cur,0); for (int i = x; i < n; ++i) { cur = cur | (1<<i); cur = cur ^ (1<<(i-x)); dzial(cur,0); } return wybr.size(); } int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); cin>> n >> m; v = vector<pair<int,int>>(m); int a,b; for(int i=0;i<m;i++){ cin >> a >> b; v[i] = {a-1,b-1}; } for (int i = 1; i <= n; ++i) { int w = ileDla(i); cout<<(w%2)<<" "; } //int w = ileDla(3); } /* 10 4 4 1 1 2 3 4 1 4 4 4 4 1 1 2 3 4 1 4 */ |