QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95965 | #5575. Knight's Tour Redux | aguo123 | TL | 2ms | 5424kb | C++14 | 1.5kb | 2023-04-12 18:58:54 | 2023-04-12 18:58:55 |
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=1e6+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+3<<endl;
cout<<pos+4<<' '<<pos+2<<endl;
cout<<pos+7<<' '<<pos+1<<endl;
cout<<pos+6<<' '<<pos+4<<endl;
cout<<pos+3<<' '<<pos+5<<endl;
cout<<pos+2<<' '<<pos+8<<endl;
cout<<pos+5<<' '<<pos+7<<endl;
cout<<pos+8<<' '<<pos+6<<endl;
cout<<pos+9<<' '<<pos+9<<endl;
for(int i=1;i<=9;i++)col[pos+i]=row[pos+i]=1,num++;
pos+=9;
}
dfs(pos+1,pos+3);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3492kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 2ms
memory: 3316kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3388kb
input:
5
output:
POSSIBLE 1 3 4 4 5 1 2 2 3 5
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3384kb
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: 3496kb
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: 3444kb
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: 3396kb
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: 0ms
memory: 3388kb
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: 3544kb
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: 3360kb
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: 2ms
memory: 3396kb
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: 3372kb
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: 3364kb
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: 3380kb
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: 0ms
memory: 3384kb
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: 0ms
memory: 3372kb
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: 0
Accepted
time: 2ms
memory: 5408kb
input:
19
output:
POSSIBLE 1 3 4 2 7 1 6 4 3 5 2 8 5 7 8 6 9 9 10 12 11 15 12 18 15 19 16 16 19 17 18 14 17 11 14 10 13 13
result:
ok answer = 1
Test #20:
score: 0
Accepted
time: 2ms
memory: 5424kb
input:
20
output:
POSSIBLE 1 3 4 2 7 1 6 4 3 5 2 8 5 7 8 6 9 9 10 12 13 13 14 16 11 17 12 20 15 19 18 18 19 15 16 14 17 11 20 10
result:
ok answer = 1
Test #21:
score: -100
Time Limit Exceeded
input:
99990
output:
POSSIBLE 1 3 4 2 7 1 6 4 3 5 2 8 5 7 8 6 9 9 10 12 13 11 16 10 15 13 12 14 11 17 14 16 17 15 18 18 19 21 22 20 25 19 24 22 21 23 20 26 23 25 26 24 27 27 28 30 31 29 34 28 33 31 30 32 29 35 32 34 35 33 36 36 37 39 40 38 43 37 42 40 39 41 38 44 41 43 44 42 45 45 46 48 49 47 52 46 51 49 48 50 47 53 50 ...