結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー ciel
提出日時 2016-12-11 23:16:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,665 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 48,680 KB
最終ジャッジ日時 2025-01-08 00:56:37
合計ジャッジ時間 1,003 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int lightsout(int, int)’:
main.cpp:84:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   84 |                 scanf("%d",&t);
      |                 ~~~~~^~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:116:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |         scanf("%d%d",&m,&n);
      |         ~~~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:63,
                 from main.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<long long unsigned int, std::allocator<long long unsigned int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long unsigned int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC target("avx")

#include <vector>
#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);

	//0解(quiet pattern)の集合tを用意する
	val_t tmsk=0;
	vector<val_t>t;
	vector<pair<int,val_t>>a_ok;
	for(int i=0;i<x*y;i++){
		if((badbits>>i)&1){
			t.push_back(a[i][0]);
		}else{
			a_ok.emplace_back(i,a[i][0]);
			tmsk|=(val_t)1<<i;
		}
	}

	//入力・解の存在判定
	val_t input=0;
	for(int i=0;i<x*y;i++){
		int t;
		scanf("%d",&t);
		input|=(val_t)t<<i;
	}
	if(any_of(t.begin(),t.end(),[&](val_t &e)->bool{
		return popcnt(e&input)&1;
	})){
		return -1;
	}

	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_ok)if(input&((val_t)1<<j.first))c0^=j.second;
	//0解の重ね合わせをすべて試す
	#pragma omp parallel for reduction(min:r0)
	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);
	int r=lightsout(n,m);
	if(r<0){
		puts("Impossible");
	}else{
		printf("%d\n",r);
	}
}
0