QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #637324 | #7263. Team Competition | syxsyx | AC ✓ | 107ms | 22916kb | C++14 | 4.4kb | 2024-10-13 12:09:22 | 2024-10-13 12:09:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=N*N;
int n;
int a[N][N];
void build(int n)
{
if(n==1)
{
a[1][1]=0;
return;
}
if(n==2)
{
a[1][2]=1;
a[2][1]=2;
return;
}
for(int i=2;i<n;i++)
{
int nowx=1,nowy=i+1;
for(int j=1;j<n;j++)
{
a[nowx][nowy]=i;
nowx=nowx%n+1;
nowy=nowy%n+1;
if(nowx==i) nowx=nowx%n+1;
if(nowy==i) nowy=nowy%n+1;
}
}
if(n%2==1)
{
int nowx=1,nowy=2;
for(int j=1;j<n;j++)
{
a[nowx][nowy]=n;
nowx=nowx%n+1;
nowy=(nowy+1)%n+1;
}
nowx=2,nowy=3;
for(int j=1;j<n;j++)
{
a[nowx][nowy]=1;
nowx=nowx%n+1;
nowy=(nowy+1)%n+1;
}
}
if(n%2==0)
{
a[1][2]=a[n/2+1][1]=a[n/2][n-1]=n;
int nowx=2,nowy=3;
for(int j=1;j<n/2-1;j++)
{
a[nowx][nowy]=n;
nowx=nowx%n+1;
nowy=(nowy+1)%n+1;
}
nowx=n/2+2,nowy=4;
for(int j=1;j<n/2-1;j++)
{
a[nowx][nowy]=n;
nowx=nowx%n+1;
nowy=(nowy+1)%n+1;
}
a[n/2][n]=a[n][n-1]=a[n/2+1][2]=1;
nowx=2,nowy=4;
for(int j=1;j<n/2-1;j++)
{
a[nowx][nowy]=1;
nowx=nowx%n+1;
nowy=(nowy+1)%n+1;
}
nowx=n/2+2,nowy=3;
for(int j=1;j<n/2-1;j++)
{
a[nowx][nowy]=1;
nowx=nowx%n+1;
nowy=(nowy+1)%n+1;
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++) printf("%d",a[i][j]);printf("\n");}
}
int cnt,ans1[M],ans2[M],ans3[M];
int deg[N][N];
bool checkans()
{
for(int i=1;i<=cnt;i++)
{
int x=ans1[i],y=ans2[i],z=ans3[i];
deg[x][y]++,deg[y][x]++;
deg[y][z]++,deg[z][y]++;
deg[x][z]++,deg[z][x]++;
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++) printf("%d ",deg[i][j]);printf("\n");}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) if(deg[i][j]!=deg[1][2]) return false;
return true;
}
void upd(int x,int y,int z)
{
cnt++;
ans1[cnt]=x;
ans2[cnt]=y;
ans3[cnt]=z;
}
void work(int l,int r)
{
int len=r-l+1;
if(len==3)
{
for(int t=1;t<=6;t++)
for(int i=l;i<=r;i++)
for(int j=i+1;j<=r;j++)
for(int k=j+1;k<=r;k++)
upd(i,j,k);
}
if(len==4)
{
for(int t=1;t<=3;t++)
for(int i=l;i<=r;i++)
for(int j=i+1;j<=r;j++)
for(int k=j+1;k<=r;k++)
upd(i,j,k);
}
if(len==5)
{
for(int t=1;t<=2;t++)
for(int i=l;i<=r;i++)
for(int j=i+1;j<=r;j++)
for(int k=j+1;k<=r;k++)
upd(i,j,k);
}
if(len==6)
{
for(int t=1;t<=3;t++)
{
upd(l+0,l+1,l+2);
upd(l+0,l+1,l+3);
upd(l+0,l+2,l+4);
upd(l+0,l+3,l+5);
upd(l+0,l+4,l+5);
upd(l+1,l+2,l+5);
upd(l+1,l+3,l+4);
upd(l+1,l+4,l+5);
upd(l+2,l+3,l+4);
upd(l+2,l+3,l+5);
}
}
if(len==7)
{
for(int t=1;t<=3;t++)
{
upd(l+0,l+1,l+2);
upd(l+0,l+1,l+2);
upd(l+0,l+3,l+4);
upd(l+0,l+3,l+4);
upd(l+0,l+5,l+6);
upd(l+0,l+5,l+6);
upd(l+1,l+3,l+5);
upd(l+1,l+3,l+5);
upd(l+1,l+4,l+6);
upd(l+1,l+4,l+6);
upd(l+2,l+3,l+6);
upd(l+2,l+3,l+6);
upd(l+2,l+4,l+5);
upd(l+2,l+4,l+5);
}
}
if(len==8)
{
for(int i=l;i<=r;i++)
for(int j=i+1;j<=r;j++)
for(int k=j+1;k<=r;k++)
upd(i,j,k);
}
}
void solve(int l,int r)
{
int len=r-l+1;
if(len<9){work(l,r);return;}
int t=len/3;
int st1=l,st2=l+t,st3=l+t+t;
int les1=r,les2=r-1;
if(len%3==0)
{
for(int i=0;i<t;i++)
for(int j=1;j<=6;j++)
upd(st1+i,st2+i,st3+i);
}
if(len%3==1)
{
for(int i=0;i<t;i++)
for(int j=1;j<=3;j++)
{
upd(st1+i,st2+i,les1);
upd(st2+i,st3+i,les1);
upd(st3+i,st1+i,les1);
upd(st1+i,st2+i,st3+i);
}
}
if(len%3==2)
{
for(int j=1;j<=2;j++)
{
upd(st1,les1,les2);
upd(st2,les1,les2);
upd(st3,les1,les2);
upd(st1,st2,les1);
upd(st2,st3,les1);
upd(st3,st1,les1);
upd(st1,st2,les2);
upd(st2,st3,les2);
upd(st3,st1,les2);
upd(st1,st2,st3);
}
for(int i=1;i<t;i++)
for(int j=1;j<=3;j++)
{
upd(st1+i,st2+i,les1);
upd(st2+i,st3+i,les1);
upd(st3+i,st1+i,les1);
upd(st1+i,st2+i,les2);
upd(st2+i,st3+i,les2);
upd(st3+i,st1+i,les2);
}
}
build(t);
for(int i=1;i<=t;i++)
for(int j=1;j<=t;j++)
if(i!=j) for(int k=1;k<=6;k++) upd(st1+a[i][j]-1,st2+i-1,st3+j-1);
solve(st1,st1+t-1);
solve(st2,st2+t-1);
solve(st3,st3+t-1);
}
int main()
{
scanf("%d",&n);
solve(1,n);
assert(checkans());
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++) printf("%d %d %d\n",ans1[i],ans2[i],ans3[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10060kb
input:
5
output:
20 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
result:
ok good.
Test #2:
score: 0
Accepted
time: 98ms
memory: 20832kb
input:
995
output:
989030 1 995 994 332 995 994 663 995 994 1 332 995 332 663 995 663 1 995 1 332 994 332 663 994 663 1 994 1 332 663 1 995 994 332 995 994 663 995 994 1 332 995 332 663 995 663 1 995 1 332 994 332 663 994 663 1 994 1 332 663 2 333 995 333 664 995 664 2 995 2 333 994 333 664 994 664 2 994 2 333 995 333...
result:
ok good.
Test #3:
score: 0
Accepted
time: 90ms
memory: 21636kb
input:
996
output:
991020 1 333 665 1 333 665 1 333 665 1 333 665 1 333 665 1 333 665 2 334 666 2 334 666 2 334 666 2 334 666 2 334 666 2 334 666 3 335 667 3 335 667 3 335 667 3 335 667 3 335 667 3 335 667 4 336 668 4 336 668 4 336 668 4 336 668 4 336 668 4 336 668 5 337 669 5 337 669 5 337 669 5 337 669 5 337 669 5 3...
result:
ok good.
Test #4:
score: 0
Accepted
time: 82ms
memory: 22132kb
input:
997
output:
993012 1 333 997 333 665 997 665 1 997 1 333 665 1 333 997 333 665 997 665 1 997 1 333 665 1 333 997 333 665 997 665 1 997 1 333 665 2 334 997 334 666 997 666 2 997 2 334 666 2 334 997 334 666 997 666 2 997 2 334 666 2 334 997 334 666 997 666 2 997 2 334 666 3 335 997 335 667 997 667 3 997 3 335 667...
result:
ok good.
Test #5:
score: 0
Accepted
time: 98ms
memory: 20936kb
input:
998
output:
995006 1 998 997 333 998 997 665 998 997 1 333 998 333 665 998 665 1 998 1 333 997 333 665 997 665 1 997 1 333 665 1 998 997 333 998 997 665 998 997 1 333 998 333 665 998 665 1 998 1 333 997 333 665 997 665 1 997 1 333 665 2 334 998 334 666 998 666 2 998 2 334 997 334 666 997 666 2 997 2 334 998 334...
result:
ok good.
Test #6:
score: 0
Accepted
time: 91ms
memory: 22916kb
input:
999
output:
997002 1 334 667 1 334 667 1 334 667 1 334 667 1 334 667 1 334 667 2 335 668 2 335 668 2 335 668 2 335 668 2 335 668 2 335 668 3 336 669 3 336 669 3 336 669 3 336 669 3 336 669 3 336 669 4 337 670 4 337 670 4 337 670 4 337 670 4 337 670 4 337 670 5 338 671 5 338 671 5 338 671 5 338 671 5 338 671 5 3...
result:
ok good.
Test #7:
score: 0
Accepted
time: 107ms
memory: 22552kb
input:
1000
output:
999000 1 334 1000 334 667 1000 667 1 1000 1 334 667 1 334 1000 334 667 1000 667 1 1000 1 334 667 1 334 1000 334 667 1000 667 1 1000 1 334 667 2 335 1000 335 668 1000 668 2 1000 2 335 668 2 335 1000 335 668 1000 668 2 1000 2 335 668 2 335 1000 335 668 1000 668 2 1000 2 335 668 3 336 1000 336 669 1000...
result:
ok good.
Test #8:
score: 0
Accepted
time: 2ms
memory: 10052kb
input:
3
output:
6 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
result:
ok good.
Test #9:
score: 0
Accepted
time: 0ms
memory: 10112kb
input:
4
output:
12 1 2 3 1 2 4 1 3 4 2 3 4 1 2 3 1 2 4 1 3 4 2 3 4 1 2 3 1 2 4 1 3 4 2 3 4
result:
ok good.
Test #10:
score: 0
Accepted
time: 0ms
memory: 9940kb
input:
5
output:
20 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
result:
ok good.
Test #11:
score: 0
Accepted
time: 1ms
memory: 10064kb
input:
6
output:
30 1 2 3 1 2 4 1 3 5 1 4 6 1 5 6 2 3 6 2 4 5 2 5 6 3 4 5 3 4 6 1 2 3 1 2 4 1 3 5 1 4 6 1 5 6 2 3 6 2 4 5 2 5 6 3 4 5 3 4 6 1 2 3 1 2 4 1 3 5 1 4 6 1 5 6 2 3 6 2 4 5 2 5 6 3 4 5 3 4 6
result:
ok good.
Test #12:
score: 0
Accepted
time: 1ms
memory: 10068kb
input:
7
output:
42 1 2 3 1 2 3 1 4 5 1 4 5 1 6 7 1 6 7 2 4 6 2 4 6 2 5 7 2 5 7 3 4 7 3 4 7 3 5 6 3 5 6 1 2 3 1 2 3 1 4 5 1 4 5 1 6 7 1 6 7 2 4 6 2 4 6 2 5 7 2 5 7 3 4 7 3 4 7 3 5 6 3 5 6 1 2 3 1 2 3 1 4 5 1 4 5 1 6 7 1 6 7 2 4 6 2 4 6 2 5 7 2 5 7 3 4 7 3 4 7 3 5 6 3 5 6
result:
ok good.
Test #13:
score: 0
Accepted
time: 1ms
memory: 10128kb
input:
8
output:
56 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 2 8 1 3 4 1 3 5 1 3 6 1 3 7 1 3 8 1 4 5 1 4 6 1 4 7 1 4 8 1 5 6 1 5 7 1 5 8 1 6 7 1 6 8 1 7 8 2 3 4 2 3 5 2 3 6 2 3 7 2 3 8 2 4 5 2 4 6 2 4 7 2 4 8 2 5 6 2 5 7 2 5 8 2 6 7 2 6 8 2 7 8 3 4 5 3 4 6 3 4 7 3 4 8 3 5 6 3 5 7 3 5 8 3 6 7 3 6 8 3 7 8 4 5 6 4 5 7 4 5 8 4 6...
result:
ok good.
Test #14:
score: 0
Accepted
time: 0ms
memory: 10144kb
input:
9
output:
72 1 4 7 1 4 7 1 4 7 1 4 7 1 4 7 1 4 7 2 5 8 2 5 8 2 5 8 2 5 8 2 5 8 2 5 8 3 6 9 3 6 9 3 6 9 3 6 9 3 6 9 3 6 9 3 4 8 3 4 8 3 4 8 3 4 8 3 4 8 3 4 8 2 4 9 2 4 9 2 4 9 2 4 9 2 4 9 2 4 9 3 5 7 3 5 7 3 5 7 3 5 7 3 5 7 3 5 7 1 5 9 1 5 9 1 5 9 1 5 9 1 5 9 1 5 9 2 6 7 2 6 7 2 6 7 2 6 7 2 6 7 2 6 7 1 6 8 1 6...
result:
ok good.
Test #15:
score: 0
Accepted
time: 1ms
memory: 10044kb
input:
10
output:
90 1 4 10 4 7 10 7 1 10 1 4 7 1 4 10 4 7 10 7 1 10 1 4 7 1 4 10 4 7 10 7 1 10 1 4 7 2 5 10 5 8 10 8 2 10 2 5 8 2 5 10 5 8 10 8 2 10 2 5 8 2 5 10 5 8 10 8 2 10 2 5 8 3 6 10 6 9 10 9 3 10 3 6 9 3 6 10 6 9 10 9 3 10 3 6 9 3 6 10 6 9 10 9 3 10 3 6 9 3 4 8 3 4 8 3 4 8 3 4 8 3 4 8 3 4 8 2 4 9 2 4 9 2 4 9 ...
result:
ok good.
Test #16:
score: 0
Accepted
time: 96ms
memory: 21760kb
input:
974
output:
947702 1 974 973 325 974 973 649 974 973 1 325 974 325 649 974 649 1 974 1 325 973 325 649 973 649 1 973 1 325 649 1 974 973 325 974 973 649 974 973 1 325 974 325 649 974 649 1 974 1 325 973 325 649 973 649 1 973 1 325 649 2 326 974 326 650 974 650 2 974 2 326 973 326 650 973 650 2 973 2 326 974 326...
result:
ok good.
Test #17:
score: 0
Accepted
time: 0ms
memory: 12512kb
input:
85
output:
7140 1 29 85 29 57 85 57 1 85 1 29 57 1 29 85 29 57 85 57 1 85 1 29 57 1 29 85 29 57 85 57 1 85 1 29 57 2 30 85 30 58 85 58 2 85 2 30 58 2 30 85 30 58 85 58 2 85 2 30 58 2 30 85 30 58 85 58 2 85 2 30 58 3 31 85 31 59 85 59 3 85 3 31 59 3 31 85 31 59 85 59 3 85 3 31 59 3 31 85 31 59 85 59 3 85 3 31 5...
result:
ok good.
Test #18:
score: 0
Accepted
time: 10ms
memory: 20328kb
input:
456
output:
207480 1 153 305 1 153 305 1 153 305 1 153 305 1 153 305 1 153 305 2 154 306 2 154 306 2 154 306 2 154 306 2 154 306 2 154 306 3 155 307 3 155 307 3 155 307 3 155 307 3 155 307 3 155 307 4 156 308 4 156 308 4 156 308 4 156 308 4 156 308 4 156 308 5 157 309 5 157 309 5 157 309 5 157 309 5 157 309 5 1...
result:
ok good.
Test #19:
score: 0
Accepted
time: 17ms
memory: 17064kb
input:
455
output:
206570 1 455 454 152 455 454 303 455 454 1 152 455 152 303 455 303 1 455 1 152 454 152 303 454 303 1 454 1 152 303 1 455 454 152 455 454 303 455 454 1 152 455 152 303 455 303 1 455 1 152 454 152 303 454 303 1 454 1 152 303 2 153 455 153 304 455 304 2 455 2 153 454 153 304 454 304 2 454 2 153 455 153...
result:
ok good.
Test #20:
score: 0
Accepted
time: 22ms
memory: 13460kb
input:
478
output:
228006 1 160 478 160 319 478 319 1 478 1 160 319 1 160 478 160 319 478 319 1 478 1 160 319 1 160 478 160 319 478 319 1 478 1 160 319 2 161 478 161 320 478 320 2 478 2 161 320 2 161 478 161 320 478 320 2 478 2 161 320 2 161 478 161 320 478 320 2 478 2 161 320 3 162 478 162 321 478 321 3 478 3 162 321...
result:
ok good.
Test #21:
score: 0
Accepted
time: 82ms
memory: 20932kb
input:
945
output:
892080 1 316 631 1 316 631 1 316 631 1 316 631 1 316 631 1 316 631 2 317 632 2 317 632 2 317 632 2 317 632 2 317 632 2 317 632 3 318 633 3 318 633 3 318 633 3 318 633 3 318 633 3 318 633 4 319 634 4 319 634 4 319 634 4 319 634 4 319 634 4 319 634 5 320 635 5 320 635 5 320 635 5 320 635 5 320 635 5 3...
result:
ok good.
Test #22:
score: 0
Accepted
time: 0ms
memory: 10976kb
input:
177
output:
31152 1 60 119 1 60 119 1 60 119 1 60 119 1 60 119 1 60 119 2 61 120 2 61 120 2 61 120 2 61 120 2 61 120 2 61 120 3 62 121 3 62 121 3 62 121 3 62 121 3 62 121 3 62 121 4 63 122 4 63 122 4 63 122 4 63 122 4 63 122 4 63 122 5 64 123 5 64 123 5 64 123 5 64 123 5 64 123 5 64 123 6 65 124 6 65 124 6 65 1...
result:
ok good.
Test #23:
score: 0
Accepted
time: 3ms
memory: 11220kb
input:
233
output:
54056 1 233 232 78 233 232 155 233 232 1 78 233 78 155 233 155 1 233 1 78 232 78 155 232 155 1 232 1 78 155 1 233 232 78 233 232 155 233 232 1 78 233 78 155 233 155 1 233 1 78 232 78 155 232 155 1 232 1 78 155 2 79 233 79 156 233 156 2 233 2 79 232 79 156 232 156 2 232 2 79 233 79 156 233 156 2 233 ...
result:
ok good.
Test #24:
score: 0
Accepted
time: 17ms
memory: 13696kb
input:
387
output:
149382 1 130 259 1 130 259 1 130 259 1 130 259 1 130 259 1 130 259 2 131 260 2 131 260 2 131 260 2 131 260 2 131 260 2 131 260 3 132 261 3 132 261 3 132 261 3 132 261 3 132 261 3 132 261 4 133 262 4 133 262 4 133 262 4 133 262 4 133 262 4 133 262 5 134 263 5 134 263 5 134 263 5 134 263 5 134 263 5 1...
result:
ok good.
Test #25:
score: 0
Accepted
time: 22ms
memory: 13992kb
input:
516
output:
265740 1 173 345 1 173 345 1 173 345 1 173 345 1 173 345 1 173 345 2 174 346 2 174 346 2 174 346 2 174 346 2 174 346 2 174 346 3 175 347 3 175 347 3 175 347 3 175 347 3 175 347 3 175 347 4 176 348 4 176 348 4 176 348 4 176 348 4 176 348 4 176 348 5 177 349 5 177 349 5 177 349 5 177 349 5 177 349 5 1...
result:
ok good.