QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95962 | #5575. Knight's Tour Redux | aguo123 | WA | 3ms | 5416kb | C++14 | 1.4kb | 2023-04-12 18:50:34 | 2023-04-12 18:50:37 |
Judging History
answer
#include<iostream>
#include<string>
#include <cstring>
#include <vector>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL N=1e5+10,mod=998244353;
int n;
int m;
string s;
int a[1000010];
LL cnt1[200],cnt2[200];
bool col[N],row[N];
int num,vis;
vector<PII>ans;
int dx[]={1,3,3,1,-1,-3,-3,-1},dy[]={3,1,-1,-3,-3,-1,1,3};
void dfs(int x,int y){
if(vis)return;
if(x<1||x>n||y<1||y>n)return;
if(col[x]||row[y])return;
num++;
col[x]=row[y]=1;
ans.push_back({x,y});
if(num==n){
for(auto k:ans)
cout<<k.first<<' '<<k.second<<endl;
vis=1;
return ;
}
for(int i=0;i<8;i++)
dfs(x+dx[i],y+dy[i]);
col[x]=row[y]=0;
num--;
ans.pop_back();
}
int main()
{ LL ans=0;
cin>>n;
if(n==1){
puts("POSSIBLE");
cout<<1<<' '<<1<<endl;
return 0;
}else if(n<5){puts("IMPOSSIBLE");return 0;}
puts("POSSIBLE");
int pos=0;
while(pos+18<n){
cout<<pos+1<<' '<<pos+1<<endl;
cout<<pos+4<<' '<<pos+2<<endl;
cout<<pos+7<<' '<<pos+3<<endl;
cout<<pos+8<<' '<<pos+6<<endl;
cout<<pos+5<<' '<<pos+5<<endl;
cout<<pos+6<<' '<<pos+8<<endl;
cout<<pos+9<<' '<<pos+9<<endl;
num++;
for(int i=1;i<=9;i++)col[pos+i]=row[pos+i]=1;
pos+=9;
}
dfs(pos+1,pos+3);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 2ms
memory: 3312kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 1ms
memory: 3328kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: 0
Accepted
time: 2ms
memory: 3440kb
input:
5
output:
POSSIBLE 1 3 4 4 5 1 2 2 3 5
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
6
output:
POSSIBLE 1 3 2 6 5 5 6 2 3 1 4 4
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
7
output:
POSSIBLE 1 3 2 6 5 7 6 4 7 1 4 2 3 5
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
8
output:
POSSIBLE 1 3 2 6 5 7 8 8 7 5 6 2 3 1 4 4
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 1ms
memory: 3316kb
input:
9
output:
POSSIBLE 1 3 2 6 3 9 6 8 9 7 8 4 7 1 4 2 5 5
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
10
output:
POSSIBLE 1 3 2 6 3 9 6 10 7 7 10 8 9 5 8 2 5 1 4 4
result:
ok answer = 1
Test #11:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
11
output:
POSSIBLE 1 3 4 4 5 7 2 8 3 11 6 10 9 9 10 6 7 5 8 2 11 1
result:
ok answer = 1
Test #12:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
12
output:
POSSIBLE 1 3 4 4 5 1 8 2 9 5 12 6 11 9 10 12 7 11 6 8 3 7 2 10
result:
ok answer = 1
Test #13:
score: 0
Accepted
time: 3ms
memory: 3356kb
input:
13
output:
POSSIBLE 1 3 2 6 5 7 4 4 3 1 6 2 7 5 8 8 9 11 12 12 13 9 10 10 11 13
result:
ok answer = 1
Test #14:
score: 0
Accepted
time: 2ms
memory: 3320kb
input:
14
output:
POSSIBLE 1 3 2 6 5 7 6 10 3 11 4 14 7 13 10 12 11 9 14 8 13 5 12 2 9 1 8 4
result:
ok answer = 1
Test #15:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
15
output:
POSSIBLE 1 3 2 6 3 9 6 10 7 13 4 12 5 15 8 14 9 11 10 8 13 7 14 4 15 1 12 2 11 5
result:
ok answer = 1
Test #16:
score: 0
Accepted
time: 0ms
memory: 3376kb
input:
16
output:
POSSIBLE 1 3 2 6 3 9 4 12 5 15 8 16 9 13 6 14 7 11 10 10 11 7 14 8 15 5 16 2 13 1 12 4
result:
ok answer = 1
Test #17:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
17
output:
POSSIBLE 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 16 14 17 11 14 12 13 15
result:
ok answer = 1
Test #18:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
18
output:
POSSIBLE 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
result:
ok answer = 1
Test #19:
score: -100
Wrong Answer
time: 2ms
memory: 5416kb
input:
19
output:
POSSIBLE 1 1 4 2 7 3 8 6 5 5 6 8 9 9
result:
wrong output format Unexpected end of file - int32 expected