結果
| 問題 |
No.3338 Whole Reverse Contradiction
|
| コンテスト | |
| ユーザー |
 kotatsugame
|
| 提出日時 | 2025-11-07 23:54:07 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 161 ms / 2,000 ms |
| コード長 | 7,558 bytes |
| コンパイル時間 | 2,061 ms |
| コンパイル使用メモリ | 114,260 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-11-07 23:54:18 |
| 合計ジャッジ時間 | 10,016 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 66 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:287:33: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
287 | for(auto[kk,v]:mp[t])
| ^
main.cpp:342:33: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
342 | for(auto[A,v]:vis)
| ^
ソースコード
#include<iostream>
#include<set>
#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();
/*
if(N==2)
{
if(mp[0].find(A_orig)==mp[0].end())return{-1};
else return mp[0][A_orig];
}
assert(N>=3);
*/
#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;
while(rc.size()>=2)
{
int x=rc.back();rc.pop_back();
int y=rc.back();rc.pop_back();
int z=0;
while(z==x||z==y)z++;
assert(z<N);
row(A,x);
col(A,0);
row(A,z);
col(A,0);
row(A,y);
col(A,0);
row(A,z);
col(A,0);
ans.push_back(x);
ans.push_back(0);
ans.push_back(z);
ans.push_back(0);
ans.push_back(y);
ans.push_back(0);
ans.push_back(z);
ans.push_back(0);
}
while(cc.size()>=2)
{
int x=cc.back();cc.pop_back();
int y=cc.back();cc.pop_back();
int z=0;
while(z==x||z==y)z++;
assert(z<N);
row(A,0);
col(A,x);
row(A,0);
col(A,z);
row(A,0);
col(A,y);
row(A,0);
col(A,z);
ans.push_back(0);
ans.push_back(x);
ans.push_back(0);
ans.push_back(z);
ans.push_back(0);
ans.push_back(y);
ans.push_back(0);
ans.push_back(z);
}
if(cc.size()==1&&rc.size()==0)
{
if(N==2)continue;
int x=0,y=1,z=2;
row(A,x);
col(A,0);
row(A,z);
col(A,0);
row(A,y);
col(A,0);
row(A,z);
col(A,0);
ans.push_back(x);
ans.push_back(0);
ans.push_back(z);
ans.push_back(0);
ans.push_back(y);
ans.push_back(0);
ans.push_back(z);
ans.push_back(0);
rc.push_back(0);
rc.push_back(1);
}
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 assert(false);
/*
else if(N%2==1&&rc.size()+1==cc.size())
{
add=true;
row(A,N/2);
ans.push_back(N/2);
for(int i=0;i<cc.size();i++)
{
col(A,cc[i]);
ans.push_back(cc[i]);
if(i<rc.size())
{
row(A,rc[i]);
ans.push_back(rc[i]);
}
}
}
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)
{
if(ans.size()%2==0)
{
int idx=x==0?i:N-i-1;
row(A,idx);
ans.push_back(idx);
}
else
{
int idx=x==0?j:N-j-1;
col(A,idx);
ans.push_back(idx);
}
}
}
//if(add)row(A,N/2),ans.push_back(N/2);
{//check
bool ok=true;
for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(A[i][j]!=VAL(i,j))ok=false;
if(!ok)continue;
}
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);
}
}
}
if(false)
{
vector<vector<int> >S={{0,7,2},{3,4,5},{6,1,8}};
auto p=solve(S);
for(int v:p)cout<<v<<" ";cout<<endl;
return 0;
}
if(false)
{
for(int N=2;N<=5;N++)
{
cout<<"N = "<<N<<endl;
map<vector<vector<int> >,vector<int> >vis;
vector<vector<int> >S(N,vector<int>(N));
for(int i=0;i<N;i++)for(int j=0;j<N;j++)S[i][j]=i*N+j;
queue<vector<vector<int> > >Q;
Q.push(S);
vis[S]={};
for(int i=0;i<N;i++)
{
auto A=S;
row(A,i);
Q.push(A);
vis[A]={i};
}
while(!Q.empty())
{
for(int x=0;x<N;x++)for(int y=0;y<N;y++)
{
auto A=Q.front();
col(A,y);
row(A,x);
if(vis.find(A)==vis.end())
{
vis[A]=vis[Q.front()];
vis[A].push_back(y);
vis[A].push_back(x);
Q.push(A);
}
}
Q.pop();
}
for(auto[A,v]:vis)
{
auto p=solve(A);
if(p==(vector<int>){-1})
{
cout<<"NA"<<endl;
for(int i=0;i<N;i++)for(int j=0;j<N;j++)cout<<A[i][j]<<(j+1==N?"\n":" ");
auto B=A;
for(int i=0;i<v.size();i++)
{
cout<<(i%2==0?"row ":"col ")<<v[v.size()-i-1]<<"\n";
if(i%2==0)row(B,v[v.size()-i-1]);
else col(B,v[v.size()-i-1]);
for(int i=0;i<N;i++)for(int j=0;j<N;j++)cout<<B[i][j]<<(j+1==N?"\n":" ");
}
return 1;
}
}
}
}
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);
}
}
}