QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#344771 | #5575. Knight's Tour Redux | Meatherm | WA | 1ms | 3884kb | C++14 | 1.4kb | 2024-03-05 09:44:44 | 2024-03-05 09:44:44 |
Judging History
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)