sumでなくxorで国勢調査する意味とは…。
https://yukicoder.me/problems/no/1421
問題
N個の変数があり、M個の式が与えられる。
各式では、いくつかの変数のxorの値が与えられる。
条件を満たす変数の割り当てをせよ。
解法
連立方程式なので、Gauss法で掃きだすだけ。
int H,W; int mat[10000][50]; int V[10000]; int R[50]; void solve() { int i,j,k,l,r,x,y; string s; cin>>W>>H; FOR(i,H) { cin>>x; FOR(j,x) { cin>>y; mat[i][y-1]=1; } cin>>V[i]; } int fix=0; FOR(i,W) { for(j=fix;j<H;j++) if(mat[j][i]) break; if(j>=H) continue; FOR(k,W) swap(mat[fix][k],mat[j][k]); swap(V[fix],V[j]); FOR(j,H) if(j!=fix&&mat[j][i]) { V[j]^=V[fix]; for(k=i;k<W;k++) mat[j][k]^=mat[fix][k]; } fix++; } FOR(i,H) { FOR(x,W) if(mat[i][x]) break; if(x<W) R[x]=V[i]; else if(V[i]) { cout<<-1<<endl; return; } } FOR(i,W) cout<<R[i]<<endl; }
まとめ
Gauss法がバグってた…。