結果

問題 No.3338 Whole Reverse Contradiction
コンテスト
ユーザー kotatsugame
提出日時 2025-11-07 23:26:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,299 bytes
コンパイル時間 1,814 ms
コンパイル使用メモリ 112,080 KB
実行使用メモリ 7,724 KB
最終ジャッジ日時 2025-11-07 23:27:03
合計ジャッジ時間 8,600 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27 WA * 29 RE * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:172:33: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  172 |                         for(auto[kk,v]:mp[t])
      |                                 ^

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cassert>
using namespace std;
void row(vector<vector<int> >&A,int idx)
{
	assert(0<=idx&&idx<A.size());
	reverse(A[idx].begin(),A[idx].end());
}
void col(vector<vector<int> >&A,int idx)
{
	assert(0<=idx&&idx<A.size());
	for(int j=0;j+j+1<A.size();j++)swap(A[j][idx],A[A.size()-j-1][idx]);
}
map<vector<vector<int> >,vector<int> >mp[2];
vector<int>solve(vector<vector<int> >A_orig)
{
	const int N=A_orig.size();
#define VAL(i,j) ((i)*N+(j))
	for(int st=0;st<2;st++)
	{
		vector<int>R(N,0),C(N,0);
		auto A=A_orig;
		auto get=[&](int i,int j,int t){
			assert(0<=i&&i<N-i-1);
			assert(0<=j&&j<N-j-1);
			int V[4]={VAL(i,j),VAL(i,N-j-1),VAL(N-i-1,j),VAL(N-i-1,N-j-1)};
			vector<vector<int> >S(2,vector<int>(2));
			auto find=[&](int v){
				for(int k=0;k<4;k++)if(V[k]==v)return k;
				return -1;
			};
			S[0][0]=find(A[i][j]);
			S[0][1]=find(A[i][N-j-1]);
			S[1][0]=find(A[N-i-1][j]);
			S[1][1]=find(A[N-i-1][N-j-1]);
			if(mp[t].find(S)==mp[t].end())return(vector<int>){-1};
			else return mp[t][S];
		};
		if(st==1)row(A,0),R[0]=1;
		for(int j=0;j<=N-j-1;j++)
		{
			if(j<N-j-1)
			{
				auto v=get(0,j,0);
				if(v==(vector<int>){-1})
				{
					C[j]=1,col(A,j);
					v=get(0,j,0);
					if(v==(vector<int>){-1})return{-1};
				}
			}
			else
			{
				int x=A[0][j],y=A[N-1][j];
				int X=VAL(0,j),Y=VAL(N-1,j);
				if(x==X&&y==Y);
				else if(x==Y&&y==X)C[j]=1,col(A,j);
				else return{-1};
			}
		}
		for(int i=1;i<=N-i-1;i++)
		{
			if(i<N-i-1)
			{
				auto v=get(i,0,0);
				if(v==(vector<int>){-1})
				{
					R[i]=1,row(A,i);
					v=get(i,0,0);
					if(v==(vector<int>){-1})return{-1};
				}
			}
			else
			{
				int x=A[i][0],y=A[i][N-1];
				int X=VAL(i,0),Y=VAL(i,N-1);
				if(x==X&&y==Y);
				else if(x==Y&&y==X)R[i]=1,row(A,i);
				else return{-1};
			}
		}
		{
			bool out=false;
			for(int i=0;i<N-i-1;i++)for(int j=0;j<N-j-1;j++)
			{
				auto v=get(i,j,0);
				if(v==(vector<int>){-1})out=true;
			}
			if(out)continue;
		}
		A=A_orig;
		vector<int>rc,cc;
		for(int i=0;i<=N-i-1;i++)if(R[i]==1)rc.push_back(i);
		for(int i=0;i<=N-i-1;i++)if(C[i]==1)cc.push_back(i);
		vector<int>ans;
		int t=0;
		if(rc.size()==cc.size())
		{
			for(int i=0;i<rc.size();i++)
			{
				row(A,rc[i]);
				ans.push_back(rc[i]);
				col(A,cc[i]);
				ans.push_back(cc[i]);
			}
			t=0;
		}
		else if(rc.size()==cc.size()+1)
		{
			for(int i=0;i<rc.size();i++)
			{
				row(A,rc[i]);
				ans.push_back(rc[i]);
				if(i<cc.size())
				{
					col(A,cc[i]);
					ans.push_back(cc[i]);
				}
			}
			t=1;
		}
		else continue;
		for(int i=0;i<N-i-1;i++)for(int j=0;j<N-j-1;j++)
		{
			auto v=get(i,j,t);
			assert(v!=(vector<int>){-1});
			for(int x:v)
			{
				int s=ans.size()%2;
				ans.push_back(s==0?x==0?i:N-i-1:x==0?j:N-j-1);
			}
		}
		return ans;
	}
	return{-1};
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int t=0;t<2;t++)
	{//mp (2 x 2)
		vector<vector<int> >S={{0,1},{2,3}};
		mp[t][S]={};
		queue<vector<vector<int> > >Q;
		Q.push(S);
		while(!Q.empty())
		{
			for(int x=0;x<2;x++)for(int y=0;y<2;y++)
			{
				vector<vector<int> >A=Q.front();
				if(t==0)col(A,y),row(A,x),col(A,y),row(A,x);
				else row(A,y),col(A,x),row(A,y),col(A,x);
				if(mp[t].find(A)==mp[t].end())
				{
					mp[t][A].push_back(x);
					mp[t][A].push_back(y);
					mp[t][A].push_back(x);
					mp[t][A].push_back(y);
					for(int v:mp[t][Q.front()])mp[t][A].push_back(v);
					Q.push(A);
				}
			}
			Q.pop();
		}
		{
			//cout<<"t = "<<t<<endl;
			for(auto[kk,v]:mp[t])
			{
				vector<vector<int> >k=kk;
				//cout<<"{{"<<k[0][0]<<", "<<k[0][1]<<"}, {"<<k[1][0]<<", "<<k[1][1]<<"}} : "<<v.size()<<endl;
				for(int i=0;i<v.size();i++)
				{
					if((i+t)%2==0)row(k,v[i]);
					else col(k,v[i]);
				}
				assert(k==S);
			}
		}
	}
	int T;cin>>T;
	for(;T--;)
	{
		int N;cin>>N;
		vector<vector<int> >A(N,vector<int>(N));
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)cin>>A[i][j],A[i][j]--;
		auto p=solve(A);
		if(p==(vector<int>){-1})cout<<"-1\n";
		else
		{
			cout<<p.size()<<"\n";
			for(int i=0;i<p.size();i++)
			{
				cout<<p[i]+1<<(i+1==p.size()?"\n":" ");
				if(i%2==0)row(A,p[i]);
				else col(A,p[i]);
			}
			for(int i=0;i<N;i++)for(int j=0;j<N;j++)assert(A[i][j]==i*N+j);
		}
	}
}
0