#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
vector<ll>s[2];
vector< pair<ll,ll> >v;
ll wyn[40];
ll jd=1;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,m,v1,v2,akt;
cin>>n>>m;
for(ll i=0;i<m;i++){
cin>>v1>>v2;
v.push_back({v1,v2});
}
for(ll i=1;i<=n;i++){//lewa granica
akt=0;
for(ll j=i;j<=n;j++){///prawa granica
akt+=(jd<<j);
s[m%2].push_back(akt);
for(ll ii=m-1;ii>=0;ii--){
// cout<<i<<' '<<j<<' '<<ii<<endl;
for(ll jj=0;jj<s[(ii%2)^1].size();jj++){
//cout<<(*it)<<' ';
if((((s[(ii%2)^1][jj])&(jd<<v[ii].first))==0&&((s[(ii%2)^1][jj])&(jd<<v[ii].second))==0)||(((s[(ii%2)^1][jj])&(jd<<v[ii].first))!=0&&((s[(ii%2)^1][jj])&(jd<<v[ii].second))!=0)){
// cout<<"mpu ";
s[ii%2].push_back(s[(ii%2)^1][jj]);
}
else if((((s[(ii%2)^1][jj]))&(jd<<v[ii].first))==0){
s[ii%2].push_back(s[(ii%2)^1][jj]);
s[ii%2].push_back(s[(ii%2)^1][jj]+(jd<<v[ii].first)-(jd<<v[ii].second));
// cout<<"dodaje dwoch debili: "<<(*it)<<' '<<(*it)+(1<<v[ii].first)-(1<<v[ii].second)<<'\n';
}
}
//cout<<endl;
//if(s[ii%2].size()>131072){
// cout<<ii<<' '<<s[ii%2].size()<<'\n';
// return 0;
//}
s[(ii%2)^1].clear();
}
wyn[j-i+1]+=s[0].size();
s[0].clear();
s[1].clear();
}
}
//for(it=wyn[1].begin();it!=wyn[1].end();it++)cout<<(*it)<<' ';
//cout<<'\n';
for(int i=1;i<=n;i++)cout<<wyn[i]%2<<' ';
return 0;
}
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 | #include<iostream> #include<vector> using namespace std; typedef long long ll; vector<ll>s[2]; vector< pair<ll,ll> >v; ll wyn[40]; ll jd=1; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,m,v1,v2,akt; cin>>n>>m; for(ll i=0;i<m;i++){ cin>>v1>>v2; v.push_back({v1,v2}); } for(ll i=1;i<=n;i++){//lewa granica akt=0; for(ll j=i;j<=n;j++){///prawa granica akt+=(jd<<j); s[m%2].push_back(akt); for(ll ii=m-1;ii>=0;ii--){ // cout<<i<<' '<<j<<' '<<ii<<endl; for(ll jj=0;jj<s[(ii%2)^1].size();jj++){ //cout<<(*it)<<' '; if((((s[(ii%2)^1][jj])&(jd<<v[ii].first))==0&&((s[(ii%2)^1][jj])&(jd<<v[ii].second))==0)||(((s[(ii%2)^1][jj])&(jd<<v[ii].first))!=0&&((s[(ii%2)^1][jj])&(jd<<v[ii].second))!=0)){ // cout<<"mpu "; s[ii%2].push_back(s[(ii%2)^1][jj]); } else if((((s[(ii%2)^1][jj]))&(jd<<v[ii].first))==0){ s[ii%2].push_back(s[(ii%2)^1][jj]); s[ii%2].push_back(s[(ii%2)^1][jj]+(jd<<v[ii].first)-(jd<<v[ii].second)); // cout<<"dodaje dwoch debili: "<<(*it)<<' '<<(*it)+(1<<v[ii].first)-(1<<v[ii].second)<<'\n'; } } //cout<<endl; //if(s[ii%2].size()>131072){ // cout<<ii<<' '<<s[ii%2].size()<<'\n'; // return 0; //} s[(ii%2)^1].clear(); } wyn[j-i+1]+=s[0].size(); s[0].clear(); s[1].clear(); } } //for(it=wyn[1].begin();it!=wyn[1].end();it++)cout<<(*it)<<' '; //cout<<'\n'; for(int i=1;i<=n;i++)cout<<wyn[i]%2<<' '; return 0; } |
English