結果
| 問題 |
No.3338 Whole Reverse Contradiction
|
| コンテスト | |
| ユーザー |
 askr58
|
| 提出日時 | 2025-11-07 23:24:58 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,897 bytes |
| コンパイル時間 | 3,701 ms |
| コンパイル使用メモリ | 303,220 KB |
| 実行使用メモリ | 7,724 KB |
| 最終ジャッジ日時 | 2025-11-07 23:25:12 |
| 合計ジャッジ時間 | 13,809 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 45 WA * 21 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
int ttt;
cin>>ttt;
random_device seed;
mt19937 rnd(seed());
while(ttt--){
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]--;
vector<int> ans;
auto fr=[&](int r)->void{
ans.push_back(r+1);
reverse(a[r].begin(),a[r].end());
};
auto fc=[&](int c)->void{
ans.push_back(c+1);
vector<int> tmp(n);
for(int i=0;i<n/2;i++)swap(a[i][c],a[n-i-1][c]);
};
vector<vector<int>> sign(n,vector<int>(n));
{
if(n%2==1){
vector<int> r(n),c(n);
vector<int> rr(n),cc(n);
for(int i=0;i<n;i++){
r[i]=a[n/2][i];
rr[i]=(n/2)*n+i;
c[i]=a[i][n/2];
cc[i]=i*n+(n/2);
}
vector<int> revr=rr,revc=cc;
reverse(revr.begin(),revr.end());
reverse(revc.begin(),revc.end());
//for(int x:r)cout<<x<<" ";
// out<<endl;
//for(int x:rr)cout<<x<<" ";
//cout<<endl;
//for(int x:revr)cout<<x<<" ";
//cout<<endl;
//for(int x:c)cout<<x<<" ";
//cout<<endl;
//for(int x:cc)cout<<x<<" ";
//cout<<endl;
//for(int x:revc)cout<<x<<" ";
//cout<<endl;
if(r==rr&&c==cc){
}else if(r==revr&&c==cc){
fr(n/2);
}else if(r==rr&&c==revc){
fr(n/2);
fc(n/2);
fr(n/2);
}else if(r==revr&&c==revc){
fr(n/2);
fc(n/2);
}else {
cout<<-1<<endl;
continue;
}
}
//for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
bool ok=true;
for(int i=0;i<n/2;i++)for(int j=0;j<n/2;j++){
vector<int> x,y;
x.push_back(i*n+j);y.push_back(a[i][j]);
x.push_back(i*n+(n-j-1));y.push_back(a[i][n-j-1]);
x.push_back((n-i-1)*n+j);y.push_back(a[n-i-1][j]);
x.push_back((n-i-1)*n+(n-j-1));y.push_back(a[n-i-1][n-j-1]);
auto z=y;
sort(z.begin(),z.end());
if(x!=z){
ok=false;
}else{
int cnt=0;
for(int s=0;s<4;s++)for(int t=s+1;t<4;t++)if(y[s]>y[t])cnt++;
for(int t:x)sign[t/n][t%n]=1-2*(cnt%2);
}
}
//for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<sign[i][j]<<(j+1==n?"\n":" ");
vector<int> rs,cs;
for(int i=0;i<n/2;i++){
if(sign[0][i]==-1){
cs.push_back(i);
for(int j=0;j<n/2;j++)sign[j][i]*=-1;
}
}
for(int i=1;i<n/2;i++){
set<int> s;
for(int j=0;j<n/2;j++){
s.insert(sign[i][j]);
}
//cout<<s.size()<<endl;
if(s.size()==2)ok=false;
else if((*s.begin())==-1){
rs.push_back(i);
for(int j=0;j<n;j++)sign[i][j]=1;
}
}
if(!ok){
cout<<-1<<endl;
continue;
}
while(cs.size()+rs.size()){
if(cs.size()&&rs.size()){
fr(rs.back());
fc(cs.back());
rs.pop_back();
cs.pop_back();
}else if(cs.size()){
fr(0);
fc(cs.back());
cs.pop_back();
fr(0);
if(!cs.empty()){
fc(cs.back());
cs.pop_back();
}
}else if(rs.size()){
fr(rs.back());
rs.pop_back();
if(!rs.empty()){
fc(0);
fr(rs.back());
rs.pop_back();
fc(0);
}
}
}
//for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
}
vector<int> todo;
for(int i=0;i<n/2;i++)for(int j=0;j<n/2;j++)todo.push_back(i*n+j);
for(int i=0;i<todo.size();i++){
int r=rnd()%(todo.size()-i);
swap(todo[r],todo[todo.size()-1-i]);
}
auto rotate=[&](int x,int y)->void{
if(ans.size()%2==0){
fr(n-x-1);
fc(n-y-1);
fr(n-x-1);
fc(n-y-1);
}else{
fc(n-y-1);
fr(n-x-1);
fc(n-y-1);
fr(n-x-1);
}
};
for(int r:todo){
//cout<<"do"<<r<<endl;
int x=r/n,y=r%n;
if(a[x][y]!=x*n+y&&a[n-x-1][y]!=(n-x-1)*n+y&&a[x][n-y-1]!=x*n+(n-y-1)&&a[n-x-1][n-y-1]!=(n-x-1)*n+(n-y-1)){
rotate(x,y);
//cout<<"rotated"<<endl;
//for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
}
if(a[x][y]==x*n+y&&a[n-x-1][y]==(n-x-1)*n+y&&a[x][n-y-1]==x*n+(n-y-1)&&a[n-x-1][n-y-1]==(n-x-1)*n+(n-y-1)){
continue;
}
if(a[x][y]==x*n+y){
rotate(x,y);
if(a[n-x-1][y]!=(n-x-1)*n+y)rotate(x,y);
}else if(a[n-x-1][y]==(n-x-1)*n+y){
rotate(n-x-1,y);
if(a[x][y]!=x*n+y)rotate(n-x-1,y);
}else if(a[x][n-y-1]==x*n+(n-y-1)){
rotate(x,n-y-1);
if(a[x][y]!=x*n+y)rotate(x,n-y-1);
}else if(a[n-x-1][n-y-1]==(n-x-1)*n+(n-y-1)){
rotate(n-x-1,n-y-1);
if(a[x][y]!=x*n+y)rotate(n-x-1,n-y-1);
}
//for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
}
vector<vector<int>> ca(n,vector<int>(n));
for(int i=0;i<n;i++)for(int j=0;j<n;j++)ca[i][j]=i*n+j;
//for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
assert(ca==a);
assert(ans.size()<=4*n*n);
}
}