結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー ciel
提出日時 2016-12-11 21:33:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,597 bytes
コンパイル時間 716 ms
コンパイル使用メモリ 70,364 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-29 04:01:16
合計ジャッジ時間 1,693 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef unsigned long long val_t;
#define popcnt __builtin_popcountll
//typedef unsigned int val_t;
//#define popcnt __builtin_popcount
//typedef mpz_class val_t;
//int popcnt(const val_t &x){int r=0;val_t z=x;for(;z;z/=2)r+=z%2;return r;}

int lightsout(int x,int y){
	vector<vector<val_t>>a(x*y);
	for(int i=0;i<x*y;i++)a[i].resize(2);

	//create problem
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			a[i+j*x][0]=(val_t)1<<(i+j*x);
			a[i+j*x][1]= 0 +
				((val_t)1<<(i+j*x)) +
				(i>0   ? (val_t)1<<(i-1+j*x) : 0) +
				(i<x-1 ? (val_t)1<<(i+1+j*x) : 0) +
				(j>0   ? (val_t)1<<(i+(j-1)*x) : 0) +
				(j<y-1 ? (val_t)1<<(i+(j+1)*x) : 0) +
				(i>0   && j>0   ? (val_t)1<<(i-1+(j-1)*x) : 0) +
				(i<x-1 && j>0   ? (val_t)1<<(i+1+(j-1)*x) : 0) +
				(i>0   && j<y-1 ? (val_t)1<<(i-1+(j+1)*x) : 0) +
				(i<x-1 && j<y-1 ? (val_t)1<<(i+1+(j+1)*x) : 0) +
				0;
		}
	}

	//solve
	val_t badbits=0;
	int i=0;
	for(;i<x*y;i++){
		if((a[i][1]&((val_t)1<<i))==0){
			int j=i+1;
			for(;j<x*y;j++){
				if((a[j][1]&((val_t)1<<i))!=0){
					swap(a[i],a[j]);
					break;
				}
			}
			if(j==x*y){
				badbits|=(val_t)1<<i;
				continue;
			}
		}

		for(int j=0;j<x*y;j++){
			if(i==j)continue;
			if((a[j][1]&((val_t)1<<i))!=0){
				a[j][0]^=a[i][0];
				a[j][1]^=a[i][1];
			}
		}
	}
	int k=x*y-popcnt(badbits);
	fprintf(stderr,"quiet pattern=%d\n",x*y-k);

	val_t input=0;
	for(int i=0;i<x*y;i++){
		int t;
		scanf("%d",&t);
		input|=(val_t)t<<i;//(x*y-1-i);
		//printf("%x\n",input);
	}

	//解の存在判定
	//for(int i=k;i<x*y;i++)

	//0解(quiet pattern)の集合tを用意する
	for(int i=k;i<x*y;i++)a[i][1]=(val_t)1<<i;
	//val_t tmsk=((val_t)1<<k)-1;
	vector<val_t>t;
	map<int,val_t>A;
	for(int i=0;i<x*y;i++){
		if((badbits>>i)&1)t.push_back(a[i][0]);
		else A[i]=a[i][0];
	}
	if(any_of(t.begin(),t.end(),[&](val_t &e)->bool{
		return popcnt(e&input)%2;
	})){
		puts("Impossible");
		exit(0);
	}

	vector<val_t>tlst(1<<(x*y-k)); // このメモリはあまり大きくならないはず
	for(val_t l=0;l<1<<(x*y-k);l++){
		val_t r=0;
		for(int j=0;j<x*y-k;j++)if(l&((val_t)1<<j))r^=t[j];
		tlst[l]=r;
	}

	val_t r0=1<<29;
	val_t c0=0;
	for(auto &j:A)if(input&((val_t)1<<j.first))c0^=j.second;
	//0解の重ね合わせをすべて試す
	for(val_t l=0;l<(val_t)1<<(x*y-k);l++){
		val_t r1=c0;
		//for(int j=0;j<x*y-k;j++)if(l&((val_t)1<<j))r1^=t[j];
		r1^=tlst[l];
		r0=min(r0,(val_t)popcnt(r1));
	}
	return r0;
}

int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%d\n",lightsout(n,m));
}
0