kmjp's blog

競技プログラミング参加記です

yukicoder : No.1421 国勢調査 (Hard)

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法がバグってた…。