QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763549#5575. Knight's Tour ReduxGold_DinoWA 1ms4132kbC++143.5kb2024-11-19 20:55:442024-11-19 20:55:45

Judging History

This is the latest submission verdict.

  • [2024-11-19 20:55:45]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4132kb
  • [2024-11-19 20:55:44]
  • Submitted

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)