小 Q 与异或
随机大法:
直到check为OK就输出
特判无解的情况就行了
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node { ll a,b; } res[1000006]; ll mp[1000006]; ll ans[1000006]; bool v[1000006]; random_device rd; uniform_int_distribution<long long> dist(0, 2e9); mt19937 gen(rd()); long long randx() { return dist(gen); } int main() { int n,m; cin>>n>>m; memset(mp,-1,sizeof mp); int flag =1; for(int i=1; i<=m; i++) { cin>>res[i].a>>res[i].b; if( mp[res[i].a]==-1) mp[res[i].a]=res[i].b; else if(mp[res[i].a]!=res[i].b) { flag=0; } } ll last =0; if(flag==0) { cout<<-1<<endl; return 0; } sort(res+1,res+1+m,[&](const node x,const node y) { return x.a<y.a; }); for(int i =1; i<=m; i++) { if(res[i].a-1==res[i-1].a&&res[i].b==res[i-1].b) { cout<<-1<<endl; return 0; } } int t=100000; while(t--) { memset(ans,0,sizeof ans); int flag =1; for(int i=1; i<=n; i++) { if(mp[i]!=-1) { ans[i]=last^mp[i]; if(ans[i]==0||ans[i]>2e10){flag =0;break;} } else { ans[i]=randx(); ans[i]++; } last^=ans[i]; } if(flag) break; } last =0; for(int i =1; i<=n; i++) { if(mp[i]!=-1) {assert(mp[i]==last^ans[i]);} assert(ans[i]<=2e10&&ans[i]>=1); cout<<ans[i]<<' '; last^=ans[i]; } }