QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#763553	#5575. Knight's Tour Redux	Gold_Dino	AC ✓	9ms	4136kb	C++14	3.5kb	2024-11-19 20:56:32	2024-11-19 20:56:32

Judging History

你现在查看的是最新测评结果

[2024-11-19 20:56:32]
评测

测评结果：AC
用时：9ms
内存：4136kb

查看

[2024-11-19 20:56:32]
提交

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 || n == 10)
        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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3936kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 1ms

memory: 3756kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 1ms

memory: 3760kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3764kb

input:

output:

POSSIBLE
3 5
4 2
1 1
2 4
5 3

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 0ms

memory: 3824kb

input:

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: 3820kb

input:

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: 3708kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 1ms

memory: 4032kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 1ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 1ms

memory: 3760kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 1ms

memory: 3780kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 8ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 9ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 8ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 8ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 4ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 8ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 8ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 4ms

memory: 3760kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 8ms

memory: 3708kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 8ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 8ms

memory: 4132kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 6ms

memory: 4136kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 3ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 2ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 3ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 3ms

memory: 3800kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 7ms

memory: 3824kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 4ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 1ms

memory: 4028kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 5ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 8ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 7ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 7ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 0ms

memory: 3888kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 3ms

memory: 3864kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 2ms

memory: 3764kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 7ms

memory: 3824kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 1ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 3ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 5ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 7ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 8ms

memory: 3764kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 6ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 5ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 4ms

memory: 3708kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 6ms

memory: 4024kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 3ms

memory: 3796kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 2ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 4ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 3ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 5ms

memory: 3760kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 3ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 5ms

memory: 3800kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 5ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 3ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 4ms

memory: 3776kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 8ms

memory: 3756kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 1ms

memory: 3768kb

input:

output:

result:

ok answer = 1