QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355947 | #5575. Knight's Tour Redux | cyc001 | RE | 1ms | 3840kb | C++23 | 1.4kb | 2024-03-17 14:11:21 | 2024-03-17 14:11:22 |
Judging History
answer
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
const vector<array<int,2>> nxt{
{-1,-3},{-1,3},{1,-3},{1,3},{-3,-1},{-3,1},{3,-1},{3,1}
};
vector<array<int,2>> qc,mxn;
vector<bool> sx,sy;
auto dfs(int n,int x,int y,int dep){
if(x>n||x<1||y>n||y<1) return;
if(sx[x]||sy[y]) return;
sx[x]=true;sy[y]=true;
qc.push_back({x,y});
auto res=[&](){
sx[x]=false;sy[y]=false;
qc.pop_back();
};
if(dep==n) throw exception();
for(const auto&[mx,my]:nxt) dfs(n,x+mx,y+my,dep+1);
res();
}
auto print(int n,int lc)->void{
if(n-lc+1>12){
if(!lc) cout<<1<<' '<<1<<'\n';
for(auto&[mx,my]:mxn) cout<<lc+mx<<' '<<lc+my<<'\n';
print(n,lc+6);
}else{
dfs(n-lc,1,1,1);
for(auto&[mx,my]:qc) if(mx>1||(!lc)){
cout<<lc+mx<<' '<<lc+my<<'\n';
}
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n;cin>>n;
if(n>1&&n<5) exit((cout<<"IMPOSSIBLE\n",0));
cout<<"POSSIBLE\n";
if(n==1){
cout<<"1 1\n";
}else if(n==5){
for(auto[ax,ay]:{make_pair(3,5),make_pair(4,2),
make_pair(1,1),make_pair(2,4),make_pair(5,3)}){
cout<<ax<<' '<<ay<<'\n';
}
}else{
mxn={{2,4},{5,5},{6,2},{3,3},{4,6},{7,7}};
print(n,0);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3636kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
5
output:
POSSIBLE 3 5 4 2 1 1 2 4 5 3
result:
ok answer = 1
Test #6:
score: -100
Runtime Error
input:
6