QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#81838 | #5575. Knight's Tour Redux | whatever# | RE | 2ms | 3532kb | C++14 | 1.3kb | 2023-02-26 14:34:01 | 2023-02-26 14:34:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int dx[8] = {-3, -3, -1, -1, 1, 1, 3, 3};
constexpr int dy[8] = {-1, 1, -3, 3, -3, 3, -1, 1};
int n, ok, dt, vx[N], vy[N];
vector<pair<int, int>> P;
void dfs(int x, int y, int st) {
if(ok) return;
P.push_back({x, y});
vx[x] = vy[y] = 1;
if(st == n) {
ok = 1;
for(auto it : P) cout << it.first + dt << " " << it.second + dt << "\n";
}
else {
for(int d = 0; d < 8; d++) {
int xx = x + dx[d], yy = y + dy[d];
if(xx < 1 || xx > n || yy < 1 || yy > n) continue;
if(!vx[xx] && !vy[yy]) dfs(xx, yy, st + 1);
}
}
vx[x] = vy[y] = 0;
P.pop_back();
}
constexpr int Dx[8] = {1, 2, 3, 6, 5, 4, 7, 8};
constexpr int Dy[8] = {1, 4, 7, 8, 5, 2, 3, 6};
int main() {
#ifdef ALEX_WEI
FILE* IN = freopen("1.in", "r", stdin);
FILE* OUT = freopen("1.out", "w", stdout);
#endif
cin >> n;
if(n == 2 || n == 3 || n == 4) cout << "IMPOSSIBLE\n", exit(0);
cout << "POSSIBLE\n";
while(n > 15) {
for(int d = 0; d < 8; d++)
cout << dt + Dx[d] << " " << dt + Dy[d] << "\n";
dt += 8, n -= 8;
}
dfs(1, 1, 1);
assert(ok);
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
/*
g++ J.cpp -o J -std=c++14 -O2 -DALEX_WEI
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3532kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 3264kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 2ms
memory: 3380kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: -100
Dangerous Syscalls
input:
5