QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #51712 | #2598. Permutation Matrix | Amalgadon# | AC ✓ | 74ms | 17300kb | C++17 | 2.9kb | 2022-10-03 16:37:38 | 2022-10-03 16:37:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int N,A[11][2030][2030];
void work(int x,int y,int n,int s,int t)
{
//cout<<x<<' '<<y<<' '<<n<<' '<<s<<' '<<t<<endl;
if(t==1)
{
for(int i=1;i<=(1<<(n-1));i++)
{
for(int j=1;j<=(1<<(n-1));j++)
{
int nx=x+i-1,ny=y+j-1;
A[n+1][nx][ny]=A[n][i][j]+s;
}
}
}
else if(t==2)
{
for(int i=1;i<=(1<<(n-1));i++)
{
for(int j=(1<<(n-1))+1;j<=(1<<n);j++)
{
int nx=x+i-1,ny=y+j-(1<<(n-1))-1;
A[n+1][nx][ny]=A[n][i][j]+s;
}
}
}
else if(t==3)
{
for(int i=(1<<(n-1))+1;i<=(1<<n);i++)
{
for(int j=1;j<=(1<<(n-1));j++)
{
int nx=x+i-(1<<(n-1))-1,ny=y+j-1;
A[n+1][nx][ny]=A[n][i][j]+s;
}
}
}
else
{
for(int i=(1<<(n-1))+1;i<=(1<<n);i++)
{
for(int j=(1<<(n-1))+1;j<=(1<<n);j++)
{
int nx=x+i-(1<<(n-1))-1,ny=y+j-(1<<(n-1))-1;
A[n+1][nx][ny]=A[n][i][j]+s;
}
}
}
}
void solve()
{
if(N==1)
{
cout<<"NO"<<endl;
return;
}
A[1][1][1]=1,A[1][1][2]=2,A[1][2][1]=3,A[1][2][2]=4;
for(int k=2;k<=10;k++)
{
//cout<<k<<"JFJJGFJG"<<endl;
int sz=(1<<(2*k)),tmp=0,cnt=0;
for(int i=1;i<=(1<<k);i+=(1<<(k-1)))
{
for(int j=1;j<=(1<<k);j+=(1<<(k-1)))
cnt++,work(i,j,k-1,tmp,cnt);
}
// for(int i=1;i<=(1<<N);i++)
// {
// for(int j=1;j<=(1<<N);j++)
// cout<<A[N][i][j]<<' ';
// cout<<endl;
// }
cnt=5,tmp+=sz/4;
for(int i=1;i<=(1<<k);i+=(1<<(k-1)))
{
for(int j=1+(1<<(k-2));j<=(1<<k);j+=(1<<(k-1)))
cnt--, work(i,j,k-1,tmp,cnt);
}
cnt=5, tmp+=sz/4;
for(int i=1+(1<<(k-2));i<=(1<<k);i+=(1<<(k-1)))
{
for(int j=1;j<=(1<<k);j+=(1<<(k-1)))
cnt--,work(i,j,k-1,tmp,cnt);
}
// for(int i=1;i<=(1<<N);i++)
// {
// for(int j=1;j<=(1<<N);j++)
// cout<<A[N][i][j]<<' ';
// cout<<endl;
// }
cnt=0,tmp+=sz/4;
for(int i=1+(1<<(k-2));i<=(1<<k);i+=(1<<(k-1)))
{
for(int j=1+(1<<(k-2));j<=(1<<k);j+=(1<<(k-1)))
cnt++,work(i,j,k-1,tmp,cnt);
}
//cout<<k<<"KKK"<<endl;
}
cout<<"YES"<<endl;
for(int i=1;i<=(1<<N);i++)
{
for(int j=1;j<=(1<<N);j++)
cout<<A[N][i][j]<<' ';
cout<<endl;
}
}
int main()
{
IOS;
cin>>N;
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3476kb
input:
1
output:
NO
result:
ok OK.
Test #2:
score: 0
Accepted
time: 1ms
memory: 17300kb
input:
2
output:
YES 1 8 2 7 12 13 11 14 3 6 4 5 10 15 9 16
result:
ok OK.
Test #3:
score: 0
Accepted
time: 2ms
memory: 17112kb
input:
3
output:
YES 1 8 20 21 2 7 19 22 12 13 25 32 11 14 26 31 36 37 49 56 35 38 50 55 41 48 60 61 42 47 59 62 3 6 18 23 4 5 17 24 10 15 27 30 9 16 28 29 34 39 51 54 33 40 52 53 43 46 58 63 44 45 57 64
result:
ok OK.
Test #4:
score: 0
Accepted
time: 9ms
memory: 17084kb
input:
4
output:
YES 1 8 20 21 68 69 81 88 2 7 19 22 67 70 82 87 12 13 25 32 73 80 92 93 11 14 26 31 74 79 91 94 36 37 49 56 97 104 116 117 35 38 50 55 98 103 115 118 41 48 60 61 108 109 121 128 42 47 59 62 107 110 122 127 132 133 145 152 193 200 212 213 131 134 146 151 194 199 211 214 137 144 156 157 204 205 2...
result:
ok OK.
Test #5:
score: 0
Accepted
time: 5ms
memory: 17192kb
input:
5
output:
YES 1 8 20 21 68 69 81 88 260 261 273 280 321 328 340 341 2 7 19 22 67 70 82 87 259 262 274 279 322 327 339 342 12 13 25 32 73 80 92 93 265 272 284 285 332 333 345 352 11 14 26 31 74 79 91 94 266 271 283 286 331 334 346 351 36 37 49 56 97 104 116 117 289 296 308 309 356 357 369 376 35 38 50 55 98 ...
result:
ok OK.
Test #6:
score: 0
Accepted
time: 4ms
memory: 17080kb
input:
6
output:
YES 1 8 20 21 68 69 81 88 260 261 273 280 321 328 340 341 1028 1029 1041 1048 1089 1096 1108 1109 1281 1288 1300 1301 1348 1349 1361 1368 2 7 19 22 67 70 82 87 259 262 274 279 322 327 339 342 1027 1030 1042 1047 1090 1095 1107 1110 1282 1287 1299 1302 1347 1350 1362 1367 12 13 25 32 73 80 92 93 265...
result:
ok OK.
Test #7:
score: 0
Accepted
time: 4ms
memory: 17144kb
input:
7
output:
YES 1 8 20 21 68 69 81 88 260 261 273 280 321 328 340 341 1028 1029 1041 1048 1089 1096 1108 1109 1281 1288 1300 1301 1348 1349 1361 1368 4100 4101 4113 4120 4161 4168 4180 4181 4353 4360 4372 4373 4420 4421 4433 4440 5121 5128 5140 5141 5188 5189 5201 5208 5380 5381 5393 5400 5441 5448 5460 5461 2 ...
result:
ok OK.
Test #8:
score: 0
Accepted
time: 18ms
memory: 17164kb
input:
8
output:
YES 1 8 20 21 68 69 81 88 260 261 273 280 321 328 340 341 1028 1029 1041 1048 1089 1096 1108 1109 1281 1288 1300 1301 1348 1349 1361 1368 4100 4101 4113 4120 4161 4168 4180 4181 4353 4360 4372 4373 4420 4421 4433 4440 5121 5128 5140 5141 5188 5189 5201 5208 5380 5381 5393 5400 5441 5448 5460 5461 16...
result:
ok OK.
Test #9:
score: 0
Accepted
time: 9ms
memory: 17084kb
input:
9
output:
YES 1 8 20 21 68 69 81 88 260 261 273 280 321 328 340 341 1028 1029 1041 1048 1089 1096 1108 1109 1281 1288 1300 1301 1348 1349 1361 1368 4100 4101 4113 4120 4161 4168 4180 4181 4353 4360 4372 4373 4420 4421 4433 4440 5121 5128 5140 5141 5188 5189 5201 5208 5380 5381 5393 5400 5441 5448 5460 5461 16...
result:
ok OK.
Test #10:
score: 0
Accepted
time: 74ms
memory: 17196kb
input:
10
output:
YES 1 8 20 21 68 69 81 88 260 261 273 280 321 328 340 341 1028 1029 1041 1048 1089 1096 1108 1109 1281 1288 1300 1301 1348 1349 1361 1368 4100 4101 4113 4120 4161 4168 4180 4181 4353 4360 4372 4373 4420 4421 4433 4440 5121 5128 5140 5141 5188 5189 5201 5208 5380 5381 5393 5400 5441 5448 5460 5461 16...
result:
ok OK.