QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#763549 | #5575. Knight's Tour Redux | Gold_Dino | WA | 1ms | 4132kb | C++14 | 3.5kb | 2024-11-19 20:55:44 | 2024-11-19 20:55:45 |
Judging History
answer
/*
author: CTZ
date: 2024/11/16
*/
#include <bits/stdc++.h>
#ifdef LOCAL__CTZ
#include "local-lib/debug.h"
#else
#define debug(...) void()
#endif
/* file-io */
/* libs */
using namespace std;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using Int = __int128_t;
using uInt = __uint128_t;
#define ris(i, a, b) for (int i = a; i <= b; ++i)
#define dro(i, a, b) for (int i = a; i >= b; --i)
const int N = 1e5 + 7;
int n;
namespace table
{
const int L = 11;
vector<pair<int, int>> tab[L + 1];
vector<int> use;
int vis1[L + 1], vis2[L + 1];
int DFS(int x, int y, vector<pair<int, int>> &v, int n)
{
// fprintf(stderr, "%d %d\n", x, y);
if (x < 1 || x > n || y < 1 || y > n)
return 0;
if (vis1[x] || vis2[y])
return 0;
vis1[x] = vis2[y] = 1;
if ((int)v.size() == n)
{
return vis1[x] = vis2[y] = 0, x == n - 2 && y == n;
}
v.push_back({x + 1, y + 3});
if (DFS(x + 1, y + 3, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x + 1, y - 3});
if (DFS(x + 1, y - 3, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x - 1, y + 3});
if (DFS(x - 1, y + 3, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x - 1, y - 3});
if (DFS(x - 1, y - 3, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x + 3, y + 1});
if (DFS(x + 3, y + 1, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x + 3, y - 1});
if (DFS(x + 3, y - 1, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x - 3, y + 1});
if (DFS(x - 3, y + 1, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
v.push_back({x - 3, y - 1});
if (DFS(x - 3, y - 1, v, n))
return vis1[x] = vis2[y] = 0, 1;
v.pop_back();
vis1[x] = vis2[y] = 0;
return 0;
}
void get()
{
for (int i = 1; i <= L; ++i)
{
tab[i].push_back({1, 1});
memset(vis1, 0, sizeof(vis1));
memset(vis2, 0, sizeof(vis2));
// fprintf(stderr, "n = %d\n", i);
if (DFS(1, 1, tab[i], i))
{
use.push_back(i);
// printf("%d\n", i);
// for (auto p : tab[i])
// printf("%d %d\n", p.first, p.second);
}
// printf("++++++\n");
}
}
}
vector<pair<int, int>> get(int n)
{
if (n == 6 || n == 8 || n == 9)
return table::tab[n];
vector<pair<int, int>> v = get(n - 1);
v.push_back({n, n});
return v;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(NULL);
table::get();
cin >> n;
if (n == 1)
{
printf("POSSIBLE\n");
printf("1 1\n");
}
else if (n == 5)
{
printf("POSSIBLE\n");
printf("3 5\n");
printf("4 2\n");
printf("1 1\n");
printf("2 4\n");
printf("5 3\n");
}
else if (n < 6)
{
printf("IMPOSSIBLE\n");
}
else
{
printf("POSSIBLE\n");
int c = n / 6 - 1;
for (int i = 1; i <= c; ++i)
for (int j = 0; j < 6; ++j)
printf("%d %d\n", (i - 1) * 6 + table::tab[6][j].first, (i - 1) * 6 + table::tab[6][j].second);
vector<pair<int, int>> re = get(n % 6 + 6);
for (auto p : re)
printf("%d %d\n", 6 * c + p.first, 6 * c + p.second);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
5
output:
POSSIBLE 3 5 4 2 1 1 2 4 5 3
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
6
output:
POSSIBLE 1 1 2 4 5 5 6 2 3 3 4 6
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
7
output:
POSSIBLE 1 1 2 4 5 5 6 2 3 3 4 6 7 7
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
8
output:
POSSIBLE 1 1 4 2 7 3 8 6 5 5 2 4 3 7 6 8
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
9
output:
POSSIBLE 1 1 4 2 3 5 2 8 5 7 6 4 9 3 8 6 7 9
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
10
output:
POSSIBLE 1 1 4 2 3 5 2 8 5 7 6 4 9 3 8 6 7 9 10 10
result:
ok answer = 1
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 3772kb
input:
11
output:
POSSIBLE 1 1 4 2 3 5 2 8 5 7 6 4 9 3 8 6 7 9 10 10 11 11
result:
wrong answer Invalid Jump from (10, 10) to (11, 11)