QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344771#5575. Knight's Tour ReduxMeathermWA 1ms3884kbC++141.4kb2024-03-05 09:44:442024-03-05 09:44:44

Judging History

This is the latest submission verdict.

  • [2024-03-05 09:44:44]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3884kb
  • [2024-03-05 09:44:44]
  • Submitted

answer

# include <bits/stdc++.h>

const int N=100010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

int dx[8]={-3,-3,-1,1,1,1,3,3};
int dy[8]={-1,1,-3,3,-3,3,-1,1};

int n;

bool l[N],c[N];

std::vector <std::pair <int,int> > d,ans,seq;

inline void ins(int x,int y){
	seq.push_back(std::make_pair(x,y));
	return;
}

void dfs(int x,int y,int dep){
	l[x]=c[y]=true,d.push_back(std::make_pair(x,y));
	
	if(dep==n){
		ans=d;//,printf("POSSIBLE! d = %llu",d.size());
		goto END;
	}
	
	for(int k=0;k<8;++k){
		int tx=x+dx[k],ty=y+dy[k];
		if(tx<1||tx>n||ty<1||ty>n||l[tx]||c[ty]) continue;
		dfs(tx,ty,dep+1);
	}
	
	END:
	l[x]=c[y]=false,d.pop_back();
	return;
}

inline void pr(void){
	puts("POSSIBLE");
	for(auto v:seq) printf("%d %d\n",v.first,v.second);
	
	exit(0);
	
	return;
}


inline void solve(int d){
	if(n-d>=12){
		ins(d+1,d+1),ins(d+4,d+2),ins(d+5,d+5),ins(d+2,d+6),ins(d+3,d+3),ins(d+6,d+4),ins(d+7,d+7);
		solve(d+6);
	}else{
		n=n-d;
		dfs(1,1,1);
		for(auto v:ans) if(v.first!=1||d==0) ins(d+v.first,d+v.second);
		pr();
	}
	return;
}

int main(void){
	n=read();
	
	if(n==1) ins(1,1),pr();
	else if(2<=n&&n<5) puts("IMPOSSIBLE"),exit(0);
	else if(n==5){
		ins(1,3),ins(4,2),ins(5,5),ins(2,4),ins(3,1);
		pr();
	}solve(0);



	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

input:

1

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

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

input:

2

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

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

input:

3

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

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

input:

4

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

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

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: 3836kb

input:

6

output:

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

result:

ok answer = 1

Test #7:

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

input:

7

output:

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

result:

ok answer = 1

Test #8:

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

input:

8

output:

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

result:

ok answer = 1

Test #9:

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

input:

9

output:

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

result:

ok answer = 1

Test #10:

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

input:

10

output:

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

result:

ok answer = 1

Test #11:

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

input:

11

output:

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

result:

ok answer = 1

Test #12:

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

input:

12

output:

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

result:

ok answer = 1

Test #13:

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

input:

13

output:

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

result:

ok answer = 1

Test #14:

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

input:

14

output:

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

result:

ok answer = 1

Test #15:

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

input:

15

output:

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

result:

ok answer = 1

Test #16:

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

input:

16

output:

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

result:

ok answer = 1

Test #17:

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

input:

17

output:

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

result:

ok answer = 1

Test #18:

score: -100
Wrong Answer
time: 0ms
memory: 3756kb

input:

18

output:

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

result:

wrong answer Invalid Jump from (7, 7) to (7, 7)