結果
| 問題 |
No.3338 Whole Reverse Contradiction
|
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2025-11-07 22:36:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,393 bytes |
| コンパイル時間 | 2,609 ms |
| コンパイル使用メモリ | 219,288 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-11-07 22:36:36 |
| 合計ジャッジ時間 | 11,053 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 54 WA * 12 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int Q;cin>>Q;
while(Q--){
int N;cin>>N;
vvi A(N,vi(N));
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin>>A[i][j];A[i][j]--;
}
}
vi ans;
bool ok=true;
bool f=true;
for(int i=0;i<N;i++){
int j=0;
if(i>=N-1-i||j>=N-1-j) continue;
vi S={i*N+j,i*N+N-1-j,(N-1-i)*N+j,(N-1-i)*N+(N-1-j)},T={A[i][j],A[i][N-1-j],A[N-1-i][j],A[N-1-i][N-1-j]};
vi SS=S,TT=T;
sort(all(SS));
sort(all(TT));
if(SS!=TT){
ok=false;
continue;
}
int pa=0;
for(int a=0;a<4;a++) for(int b=a+1;b<4;b++) if(T[a]>T[b]) pa++;
if(pa&1){
if(!f){
ans.pb(N/2);
for(int a=0;a<N/2;a++) swap(A[a][N/2],A[N-1-a][N/2]);
f=true;
}
ans.pb(i);
for(int a=0;a<N/2;a++) swap(A[i][a],A[i][N-1-a]);
f=false;
}
}
for(int j=1;j<N;j++){
int i=0;
if(i>=N-1-i||j>=N-1-j) continue;
vi S={i*N+j,i*N+N-1-j,(N-1-i)*N+j,(N-1-i)*N+(N-1-j)},T={A[i][j],A[i][N-1-j],A[N-1-i][j],A[N-1-i][N-1-j]};
vi SS=S,TT=T;
sort(all(SS));
sort(all(TT));
if(SS!=TT){
ok=false;
continue;
}
int pa=0;
for(int a=0;a<4;a++) for(int b=a+1;b<4;b++) if(T[a]>T[b]) pa++;
if(pa&1){
if(f){
ans.pb(N/2);
for(int a=0;a<N/2;a++) swap(A[N/2][a],A[N/2][N-1-a]);
f=false;
}
ans.pb(j);
for(int a=0;a<N/2;a++) swap(A[a][j],A[N-1-a][j]);
f=true;
}
}
if(N>=2){
int i=N/2-1,j=0;
vi S={i*N+j,i*N+N-1-j,(N-1-i)*N+j,(N-1-i)*N+(N-1-j)},T={A[i][j],A[i][N-1-j],A[N-1-i][j],A[N-1-i][N-1-j]};
vi SS=S,TT=T;
sort(all(SS));
sort(all(TT));
if(SS!=TT){
ok=false;
}else{
int pa=0;
for(int a=0;a<4;a++) for(int b=a+1;b<4;b++) if(T[a]>T[b]) pa++;
if(pa&1){
if(!f){
ans.pb(N/2);
for(int a=0;a<N/2;a++) swap(A[a][N/2],A[N-1-a][N/2]);
f=true;
}
ans.pb(i);
for(int a=0;a<N/2;a++) swap(A[i][a],A[i][N-1-a]);
f=false;
}
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i>=N-1-i||j>=N-1-j) continue;
vi S={i*N+j,i*N+N-1-j,(N-1-i)*N+j,(N-1-i)*N+(N-1-j)},T={A[i][j],A[i][N-1-j],A[N-1-i][j],A[N-1-i][N-1-j]};
vi SS=S,TT=T;
sort(all(SS));
sort(all(TT));
if(SS!=TT){
ok=false;
continue;
}
//cout<<i<<" "<<j<<" "<<ok<<endl;
for(int t=0;t<4;t++){
if(S[0]==T[t]){
if(t==0){
}else if(t==1){
if(f){
ans.pb(i);
ans.pb(j);
ans.pb(i);
ans.pb(j);
}else{
ans.pb(j);
ans.pb(i);
ans.pb(j);
ans.pb(i);
ans.pb(j);
ans.pb(i);
ans.pb(j);
ans.pb(i);
}
int a=T[0],b=T[1],c=T[2];
T[0]=b;
T[1]=c;
T[2]=a;
}else if(t==2){
if(f){
ans.pb(N-1-i);
ans.pb(j);
ans.pb(N-1-i);
ans.pb(j);
}else{
ans.pb(j);
ans.pb(N-1-i);
ans.pb(j);
ans.pb(N-1-i);
ans.pb(j);
ans.pb(N-1-i);
ans.pb(j);
ans.pb(N-1-i);
}
int a=T[0],b=T[2],c=T[3];
T[0]=b;
T[2]=c;
T[3]=a;
}else{
if(f){
ans.pb(i);
ans.pb(N-1-j);
ans.pb(i);
ans.pb(N-1-j);
}else{
ans.pb(N-1-j);
ans.pb(i);
ans.pb(N-1-j);
ans.pb(i);
ans.pb(N-1-j);
ans.pb(i);
ans.pb(N-1-j);
ans.pb(i);
}
int a=T[0],b=T[1],c=T[3];
T[0]=c;
T[1]=a;
T[3]=b;
}
break;
}
}
for(int t=1;t<4;t++){
if(S[1]==T[t]){
if(t==1){
}else if(t==2){
if(f){
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
}else{
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
}
for(int q=0;q<2;q++){
int a=T[1],b=T[2],c=T[3];
T[1]=c;
T[2]=a;
T[3]=b;
}
}else{
if(f){
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
}else{
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
ans.pb(N-1-j);
ans.pb(N-1-i);
}
for(int q=0;q<1;q++){
int a=T[1],b=T[2],c=T[3];
T[1]=c;
T[2]=a;
T[3]=b;
}
}
break;
}
}
if(S[2]!=T[2]||S[3]!=T[3]){
ok=false;
continue;
}
}
}
if(N&1){
if(A[N/2][0]!=(N/2)*N){
if(A[0][N/2]!=N/2){
ans.pb(N/2);
ans.pb(N/2);
for(int j=0;j<N/2;j++) swap(A[N/2][j],A[N/2][N-1-j]);
for(int j=0;j<N/2;j++) swap(A[j][N/2],A[N-1-j][N/2]);
}else{
if(f){
ans.pb(N/2);
for(int j=0;j<N/2;j++) swap(A[N/2][j],A[N/2][N-1-j]);
}else{
ans.pb(N/2);
ans.pb(N/2);
ans.pb(N/2);
for(int j=0;j<N/2;j++) swap(A[N/2][j],A[N/2][N-1-j]);
}
}
}else{
if(A[0][N/2]!=N/2){
if(f){
ans.pb(N/2);
ans.pb(N/2);
ans.pb(N/2);
for(int j=0;j<N/2;j++) swap(A[N/2][j],A[N/2][N-1-j]);
for(int j=0;j<N/2;j++) swap(A[j][N/2],A[N-1-j][N/2]);
for(int j=0;j<N/2;j++) swap(A[N/2][j],A[N/2][N-1-j]);
}else{
ans.pb(N/2);
for(int j=0;j<N/2;j++) swap(A[j][N/2],A[N-1-j][N/2]);
}
}else{
}
}
for(int j=0;j<N;j++) ok&=(A[N/2][j]==(N/2)*N+j);
for(int j=0;j<N;j++) ok&=(A[j][N/2]==j*N+(N/2));
}
if(ok){
if(si(ans)>4*N*N){
assert(N==2);
}
cout<<si(ans)<<"\n";
for(int x:ans) cout<<x+1<<" ";
cout<<"\n";
}else{
cout<<-1<<"\n";
}
}
}