QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95115#5575. Knight's Tour Reduxpedroteosousa#WA 2ms3764kbC++202.2kb2023-04-09 07:35:562023-04-09 07:35:57

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-09 07:35:57]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3764kb
Show
  • [2023-04-09 07:35:56]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> resp;

int sub[10][2] = {
	{0, 0},
	{3, 1},
	{6, 2},
	{9, 3},
	{2, 4},
	{5, 5},
	{8, 6},
	{1, 7},
	{4, 8},
	{7, 9},
};

int m[20][20][2] = {
{{0, 0}},{},{},{},{},
{{0, 2},{3, 1},{4, 4},{1, 3},{2, 0},},

{{0, 0},{1, 3},{4, 2},{5, 5},{2, 4},{3, 1},},

{{0, 0},{1, 3},{2, 6},{5, 5},{6, 2},{3, 1},{4, 4},},

{{0, 0},{1, 3},{2, 6},{5, 7},{4, 4},{3, 1},{6, 2},{7, 5},},

{{0, 0},{1, 3},{2, 6},{5, 7},{4, 4},{3, 1},{6, 2},{7, 5},{8, 8},},

{{0, 0},{1, 3},{2, 6},{3, 9},{6, 8},{5, 5},{4, 2},{7, 1},{8, 4},{9, 7},},

{{0, 0},{1, 3},{2, 6},{3, 9},{6, 8},{5, 5},{4, 2},{7, 1},{8, 4},{9, 7},{10, 10},},

{{0, 0},{1, 3},{4, 2},{7, 1},{8, 4},{11, 5},{10, 8},{9, 11},{6, 10},{5, 7},{2, 6},{3, 9},},

{{0, 0},{1, 3},{4, 4},{5, 1},{2, 2},{3, 5},{6, 6},{7, 9},{8, 12},{11, 11},{12, 8},{9, 7},{10, 10},},

{{0, 0},{1, 3},{2, 6},{5, 7},{4, 4},{3, 1},{6, 2},{7, 5},{8, 8},{9, 11},{12, 10},{13, 13},{10, 12},{11, 9},},

{{0, 0},{1, 3},{2, 6},{5, 7},{4, 4},{3, 1},{6, 2},{7, 5},{8, 8},{9, 11},{10, 14},{13, 13},{14, 10},{11, 9},{12, 12},},

{{0, 0},{1, 3},{2, 6},{3, 9},{6, 8},{5, 5},{4, 2},{7, 1},{8, 4},{9, 7},{10, 10},{11, 13},{14, 12},{15, 15},{12, 14},{13, 11},},

{{0, 0},{1, 3},{2, 6},{3, 9},{4, 12},{5, 15},{8, 16},{9, 13},{6, 14},{7, 11},{10, 10},{11, 7},{12, 4},{13, 1},{16, 2},{15, 5},{14, 8},},

{{0, 0},{1, 3},{2, 6},{3, 9},{6, 8},{5, 5},{4, 2},{7, 1},{8, 4},{9, 7},{10, 10},{11, 13},{12, 16},{15, 17},{14, 14},{13, 11},{16, 12},{17, 15},},

{{0, 0},{1, 3},{2, 6},{3, 9},{4, 12},{7, 13},{8, 16},{5, 15},{6, 18},{9, 17},{10, 14},{11, 11},{14, 10},{15, 7},{18, 8},{17, 5},{16, 2},{13, 1},{12, 4},},
};

void solve(int n) {
	if (n > 1 && n <= 4) return;
	int x = 0, y = 0;
	while (true) {
		if (n <= 19) {
			for (int i = 0; i < n; i++) {
				resp.push_back({x + m[n][i][0], y + m[n][i][1]});
			}
			break;
		}
		for (int i = 0; i < 10; i++) {
			resp.push_back({x + sub[i][0], y + sub[i][1]});
			if (resp.size() == n) return;
		}
		x += 10;
		y += 10;
		n -= 10;
	}
}

int main() {
	int n; scanf("%d", &n);
	solve(n);
	if (resp.size() == 0) {
		printf("IMPOSSIBLE\n");
	} else {
		printf("POSSIBLE\n");
		for (auto rr: resp) {
			printf("%d %d\n", rr.first + 1, rr.second + 1);
		}
	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3568kb

input:

1

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

2

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

3

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

4

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

5

output:

POSSIBLE
1 3
4 2
5 5
2 4
3 1

result:

ok answer = 1

Test #6:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

6

output:

POSSIBLE
1 1
2 4
5 3
6 6
3 5
4 2

result:

ok answer = 1

Test #7:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

7

output:

POSSIBLE
1 1
2 4
3 7
6 6
7 3
4 2
5 5

result:

ok answer = 1

Test #8:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

8

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6

result:

ok answer = 1

Test #9:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

9

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9

result:

ok answer = 1

Test #10:

score: 0
Accepted
time: 2ms
memory: 3756kb

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

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

input:

12

output:

POSSIBLE
1 1
2 4
5 3
8 2
9 5
12 6
11 9
10 12
7 11
6 8
3 7
4 10

result:

ok answer = 1

Test #13:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

13

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
9 13
12 12
13 9
10 8
11 11

result:

ok answer = 1

Test #14:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

14

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 11
14 14
11 13
12 10

result:

ok answer = 1

Test #15:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

15

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 14
15 11
12 10
13 13

result:

ok answer = 1

Test #16:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

16

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
15 13
16 16
13 15
14 12

result:

ok answer = 1

Test #17:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

17

output:

POSSIBLE
1 1
2 4
3 7
4 10
5 13
6 16
9 17
10 14
7 15
8 12
11 11
12 8
13 5
14 2
17 3
16 6
15 9

result:

ok answer = 1

Test #18:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

18

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

result:

ok answer = 1

Test #19:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

19

output:

POSSIBLE
1 1
2 4
3 7
4 10
5 13
8 14
9 17
6 16
7 19
10 18
11 15
12 12
15 11
16 8
19 9
18 6
17 3
14 2
13 5

result:

ok answer = 1

Test #20:

score: -100
Wrong Answer
time: 1ms
memory: 3600kb

input:

20

output:

POSSIBLE
1 1
4 2
7 3
10 4
3 5
6 6
9 7
2 8
5 9
8 10
11 11
12 14
13 17
14 20
17 19
16 16
15 13
18 12
19 15
20 18

result:

wrong answer Invalid Jump from (10, 4) to (3, 5)
English 繁體中文 简体中文

Server Time: 2025-04-08 13:43:21 | OpenSource Project