QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#915873#5575. Knight's Tour ReduxtsaiWA 9ms3840kbC++145.4kb2025-02-26 16:45:432025-02-26 16:45:49

Judging History

This is the latest submission verdict.

  • [2025-02-26 16:45:49]
  • Judged
  • Verdict: WA
  • Time: 9ms
  • Memory: 3840kb
Show
  • [2025-02-26 16:45:43]
  • Submitted

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%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%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;	
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3840kb

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: 1ms
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: 0ms
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: 1ms
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: 0ms
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: 0ms
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: 0ms
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: 9ms
memory: 3584kb

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: 7ms
memory: 3840kb

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: 7ms
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: -100
Wrong Answer
time: 0ms
memory: 3840kb

input:

99993

output:

IMPOSSIBLE

result:

wrong answer jury has the better answer: jans = 1, pans = 0 (1 is Possible)
English 繁體中文 简体中文

伺服器時間: 2025-04-04 03:49:37 | 開源專案