QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #915915 | #5575. Knight's Tour Redux | tsai | WA | 8ms | 3840kb | C++14 | 6.8kb | 2025-02-26 17:17:39 | 2025-02-26 17:17:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[33];
void solve(){
int n;
scanf("%d",&n);
if(n==1){
printf("POSSIBLE\n1 1");
return ;
}else if(n==12){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
printf("6 6\n9 7\n12 8\n11 11\n8 12\n7 9\n10 10\n");
return ;
}else if(n>11&&(n-11)%9==0&&(n-11)%18!=0){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
int x=6,y=6;
int jd=0,jd1=0;
int cnt=0,k=0;
for(int i=1;i<=n-11;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y++;
}else if(jd1==1){
x+=3;y--;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
printf("%d %d\n",n-3,n-5);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-2,n-2);
return ;
}
if(n%9==0){
printf("POSSIBLE\n");
int x=n,y=n;
int k=0;
int jd=0;
int jd1=0;
int cnt=0;
for(int i=1;i<=n;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
}else if(n%9==1){
printf("POSSIBLE\n");
int x=2,y=4;
int jd=0,jd1=0;
int cnt=0,k=0;
printf("1 1\n");
for(int i=2;i<=n;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y--;
}else if(jd1==1){
x+=3;y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
}else if(n>9&&n%9==2&&(n-2)%18!=0){
printf("POSSIBLE\n");
int x=2,y=4;
int jd=0,jd1=0;
int cnt=0,k=0;
printf("1 1\n");
for(int i=2;i<=n-1;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y--;
}else if(jd1==1){
x+=3;y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
printf("%d %d\n",n,n);
}else if(n%18==12&&n>18){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
int x=6,y=6;
int jd=0,jd1=1;
int cnt=0,k=0;
for(int i=1;i<=n-12;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y--;
}else if(jd1==1){
x+=3;y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
printf("%d %d\n",n-6,n-6);
printf("%d %d\n",n-3,n-5);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-2,n-2);
}else if(n%9==8){
printf("POSSIBLE\n");
int x=n,y=n-2;
int jd=0,jd1=0;
int cnt=1,k=1;
for(int i=1;i<=n;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
// printf("%d %d\n",n,n);
}else if(n%9==7){
printf("POSSIBLE\n");
printf("%d %d\n",n-2,n-2);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-3,n-5);
printf("%d %d\n",n-6,n-6);
int x=n-7,y=n-9;
int k=0;
int jd=0;
int jd1=1;
int cnt=0;
for(int i=1;i<=n-7;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
}else if(n%9==5||(n%9==4&&n>9&&(n-4)%18!=0)){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n");
int x=6,y=6;
int jd=0,jd1=0;
int cnt=0,k=0;
for(int i=1;i<=n-5;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y++;
}else if(jd1==1){
x+=3;y--;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
}else if(n%18==3&&n>18){
printf("POSSIBLE\n5 3\n2 4\n1 1\n4 2\n3 5\n6 6\n");
int x=7,y=9;
int jd=0,jd1=1;
int cnt=0,k=0;
for(int i=1;i<=n-12;i++){
printf("%d %d\n",x,y);
k++;
cnt++;
if(k%9==0){
k=0;
x++;y+=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
if(cnt%3==0){
if(jd1==0){
x+=3;y++;
}else if(jd1==1){
x+=3;y--;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x++;y+=3;
}else if(jd==1){
x--;y-=3;
}
}
printf("%d %d\n",n-5,n-5);
printf("%d %d\n",n-2,n-4);
printf("%d %d\n",n-3,n-1);
printf("%d %d\n",n,n);
printf("%d %d\n",n-1,n-3);
printf("%d %d\n",n-4,n-2);
}else if(n%9==6){
printf("POSSIBLE\n");
printf("%d %d\n",n-2,n-2);
printf("%d %d\n",n-5,n-3);
printf("%d %d\n",n-4,n);
printf("%d %d\n",n-1,n-1);
printf("%d %d\n",n,n-4);
printf("%d %d\n",n-3,n-5);
int x=n-6,y=n-6;
int k=0;
int jd=0;
int jd1=0;
int cnt=0;
for(int i=1;i<=n-6;i++){
printf("%d %d\n",x,y);
k++;
if(k%9==0){
k=0;
x--;
y-=3;
jd1++;
jd1%=2;
jd=0;
cnt=0;
continue;
}
cnt++;
if(cnt%3==0){
if(jd1==0){
x-=3;
y--;
}else if(jd1==1){
x-=3;
y++;
}
jd++;
jd%=2;
cnt=0;
continue;
}
if(jd==0){
x--;
y-=3;
}else if(jd==1){
y+=3;
x++;
}
}
}else{
printf("IMPOSSIBLE");
}
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
6
output:
POSSIBLE 4 4 1 3 2 6 5 5 6 2 3 1
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
7
output:
POSSIBLE 5 5 2 4 3 7 6 6 7 3 4 2 1 1
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8
output:
POSSIBLE 8 6 7 3 4 2 5 5 6 8 3 7 2 4 1 1
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
9
output:
POSSIBLE 9 9 8 6 7 3 4 2 5 5 6 8 3 7 2 4 1 1
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
10
output:
POSSIBLE 1 1 2 4 3 7 4 10 7 9 6 6 5 3 8 2 9 5 10 8
result:
ok answer = 1
Test #11:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
11
output:
POSSIBLE 1 1 2 4 3 7 4 10 7 9 6 6 5 3 8 2 9 5 10 8 11 11
result:
ok answer = 1
Test #12:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
12
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5 6 6 9 7 12 8 11 11 8 12 7 9 10 10
result:
ok answer = 1
Test #13:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
13
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5 6 6 7 9 8 12 11 13 10 10 9 7 12 8 13 11
result:
ok answer = 1
Test #14:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
14
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5 6 6 7 9 8 12 11 13 10 10 9 7 12 8 13 11 14 14
result:
ok answer = 1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
15
output:
POSSIBLE 13 13 10 12 11 15 14 14 15 11 12 10 9 9 8 6 7 3 4 2 5 5 6 8 3 7 2 4 1 1
result:
ok answer = 1
Test #16:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
16
output:
POSSIBLE 14 14 11 13 12 16 15 15 16 12 13 11 10 10 9 7 8 4 7 1 4 2 5 5 6 8 3 9 2 6 1 3
result:
ok answer = 1
Test #17:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
17
output:
POSSIBLE 17 15 16 12 13 11 14 14 15 17 12 16 11 13 10 10 9 7 8 4 7 1 4 2 5 5 6 8 3 9 2 6 1 3
result:
ok answer = 1
Test #18:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
18
output:
POSSIBLE 18 18 17 15 16 12 13 11 14 14 15 17 12 16 11 13 10 10 9 7 8 4 7 1 4 2 5 5 6 8 3 9 2 6 1 3
result:
ok answer = 1
Test #19:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
19
output:
POSSIBLE 1 1 2 4 3 7 4 10 7 9 6 6 5 3 8 2 9 5 10 8 11 11 12 14 13 17 16 18 15 15 14 12 17 13 18 16 19 19
result:
ok answer = 1
Test #20:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
20
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5 6 6 7 9 8 12 11 13 10 10 9 7 12 8 13 11 14 14 17 15 20 16 19 19 16 20 15 17 18 18
result:
ok answer = 1
Test #21:
score: 0
Accepted
time: 8ms
memory: 3840kb
input:
99990
output:
POSSIBLE 99990 99990 99989 99987 99988 99984 99985 99983 99986 99986 99987 99989 99984 99988 99983 99985 99982 99982 99981 99979 99980 99976 99979 99973 99976 99974 99977 99977 99978 99980 99975 99981 99974 99978 99973 99975 99972 99972 99971 99969 99970 99966 99967 99965 99968 99968 99969 99971 999...
result:
ok answer = 1
Test #22:
score: 0
Accepted
time: 8ms
memory: 3712kb
input:
99991
output:
POSSIBLE 1 1 2 4 3 7 4 10 7 9 6 6 5 3 8 2 9 5 10 8 11 11 12 14 13 17 16 18 15 15 14 12 17 13 18 16 19 19 20 22 21 25 22 28 25 27 24 24 23 21 26 20 27 23 28 26 29 29 30 32 31 35 34 36 33 33 32 30 35 31 36 34 37 37 38 40 39 43 40 46 43 45 42 42 41 39 44 38 45 41 46 44 47 47 48 50 49 53 52 54 51 51 50 ...
result:
ok answer = 1
Test #23:
score: 0
Accepted
time: 8ms
memory: 3840kb
input:
99992
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5 6 6 7 9 8 12 11 13 10 10 9 7 12 8 13 11 14 14 15 17 16 20 17 23 20 22 19 19 18 16 21 15 22 18 23 21 24 24 25 27 26 30 29 31 28 28 27 25 30 26 31 29 32 32 33 35 34 38 35 41 38 40 37 37 36 34 39 33 40 36 41 39 42 42 43 45 44 48 47 49 46 46 45 43 48 44 49 47 50 50 51 53 52 ...
result:
ok answer = 1
Test #24:
score: 0
Accepted
time: 5ms
memory: 3840kb
input:
99993
output:
POSSIBLE 5 3 2 4 1 1 4 2 3 5 6 6 7 9 8 12 9 15 12 14 11 11 10 8 13 7 14 10 15 13 16 16 17 19 18 22 21 23 20 20 19 17 22 18 23 21 24 24 25 27 26 30 27 33 30 32 29 29 28 26 31 25 32 28 33 31 34 34 35 37 36 40 39 41 38 38 37 35 40 36 41 39 42 42 43 45 44 48 45 51 48 50 47 47 46 44 49 43 50 46 51 49 52 ...
result:
ok answer = 1
Test #25:
score: -100
Wrong Answer
time: 0ms
memory: 3840kb
input:
99994
output:
IMPOSSIBLE
result:
wrong answer jury has the better answer: jans = 1, pans = 0 (1 is Possible)