QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#81738	#5575. Knight's Tour Redux	feecle6418	AC ✓	55ms	13592kb	C++14	1.7kb	2023-02-26 10:36:23	2023-02-26 10:38:27

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-02-26 10:38:27]
评测

测评结果：AC
用时：55ms
内存：13592kb

查看

[2023-02-26 10:36:23]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
int n,nn,is1[150],is2[150],a[150],b[150],D;
int dx[]={1,3,1,3,-1,-3,-1,-3};
int dy[]={3,1,-3,-1,3,1,-3,-1};
int my[20][20]={
{0,0},
{1,1},
{2,4},
{3,7},
{4,10},
{7,9},
{6,6},
{5,3},
{8,2},
{9,5},
{10,8}
};
int A[100005],B[100005];
void dfs(int x,int y,int num){
	a[num]=x,b[num]=y;
	if(num==n){
		for(int i=1;i<=num;i++){
			cout<<a[i]+D<<' '<<b[i]+D<<'\n';
			A[++A[0]]=a[i]+D;
			B[A[0]]=b[i]+D;
		}
		assert(A[0]==nn);
		set<int> s1,s2;
		s1.insert(A[nn]),s2.insert(B[nn]);
		for(int i=1;i<nn;i++){
			bool ok=0;
			for(int j=0;j<8;j++){
				if(A[i]+dx[j]==A[i+1]&&B[i]+dy[j]==B[i+1])ok=1;
			}
			if(!ok)assert(0);
			s1.insert(A[i]),s2.insert(B[i]);
		}
		assert(s1.size()==nn&&s2.size()==nn);
		exit(0);
	}
	is1[x]=is2[y]=1;
	for(int i=0;i<8;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>n)continue;
		if(is1[nx]||is2[ny])continue;
		dfs(nx,ny,num+1);
	}
	is1[x]=is2[y]=0;
}
int main(){
	cin>>n,nn=n;
	if(n==2||n==3||n==4)return puts("IMPOSSIBLE"),0;
	puts("POSSIBLE");
	if(n==5){
		dfs(1,3,1);
	}
	if(n==1){
		dfs(1,1,1);
	}
	if(n%10>=6||n%10==0){
		for(int i=1;i<=n/10;i++){
			for(int j=1;j<=10;j++){
				cout<<my[j][0]+(i-1)*10<<' '<<my[j][1]+(i-1)*10<<'\n';
				A[++A[0]]=my[j][0]+(i-1)*10;
				B[A[0]]=my[j][1]+(i-1)*10;
			}
		}
		if(n%10==0)exit(0);
		D=n/10*10;
		n%=10;
		dfs(1,1,1);
	}
	else {
		for(int i=1;i<n/10;i++){
			for(int j=1;j<=10;j++){
				cout<<my[j][0]+(i-1)*10<<' '<<my[j][1]+(i-1)*10<<'\n';
				A[++A[0]]=my[j][0]+(i-1)*10;
				B[A[0]]=my[j][1]+(i-1)*10;
			}
		}
		if(n%10==0)exit(0);
		D=n/10*10-10;
		n-=D;
		dfs(1,1,1);
	}
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3476kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 0ms

memory: 3492kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 2ms

memory: 3468kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 2ms

memory: 3476kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3404kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 0ms

memory: 3436kb

input:

output:

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

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 2ms

memory: 3408kb

input:

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: 0ms

memory: 3400kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 0ms

memory: 3372kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 2ms

memory: 3380kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 0ms

memory: 3408kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 2ms

memory: 3396kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 2ms

memory: 3408kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 0ms

memory: 3412kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 1ms

memory: 3368kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 0ms

memory: 3484kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 2ms

memory: 3372kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 1ms

memory: 3444kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 2ms

memory: 3496kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 16ms

memory: 4208kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 46ms

memory: 13552kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 49ms

memory: 13584kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 49ms

memory: 13544kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 50ms

memory: 13520kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 36ms

memory: 13520kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 55ms

memory: 13592kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 46ms

memory: 13548kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 47ms

memory: 13556kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 33ms

memory: 13520kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 16ms

memory: 4176kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 29ms

memory: 10956kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 13ms

memory: 5972kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 17ms

memory: 7588kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 9ms

memory: 6592kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 11ms

memory: 7204kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 37ms

memory: 11608kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 41ms

memory: 12604kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 2ms

memory: 3556kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 32ms

memory: 9068kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 35ms

memory: 13232kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 19ms

memory: 11388kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 34ms

memory: 12428kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 32ms

memory: 9632kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 17ms

memory: 6792kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 23ms

memory: 8908kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 12ms

memory: 5448kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 11ms

memory: 4032kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 0ms

memory: 4124kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 41ms

memory: 10792kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 20ms

memory: 9612kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 33ms

memory: 11356kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 40ms

memory: 12868kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 4ms

memory: 3992kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 7ms

memory: 4460kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 22ms

memory: 9104kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 14ms

memory: 7996kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 34ms

memory: 10500kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 13ms

memory: 5956kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 4ms

memory: 4864kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 11ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 20ms

memory: 7028kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 19ms

memory: 8564kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 6ms

memory: 6144kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 25ms

memory: 9184kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 17ms

memory: 8792kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 6ms

memory: 5888kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 9ms

memory: 7012kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 37ms

memory: 12532kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 46ms

memory: 13580kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 2ms

memory: 4028kb

input:

output:

result:

ok answer = 1