QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#916016	#5575. Knight's Tour Redux	REN5511	AC ✓	11ms	4224kb	C++23	3.4kb	2025-02-26 18:27:19	2025-02-26 18:27:29

Judging History

This is the latest submission verdict.

[2025-02-26 18:27:29]
Judged

Verdict: AC
Time: 11ms
Memory: 4224kb

Show

[2025-02-26 18:27:19]
Submitted

answer

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
int n;
int dirc[8][2] = { {1, 3}, {3, -1}, {-1, -3}, {-3, 1}, {1, -3}, {3, 1}, {-1, 3}, {-3, -1} };
int row[10005];
int col[10005];
int cntr = 0, cntl = 0;
deque<pair<int, int>> q;
deque<pair<int, int>> ansq;
vector<pair<int, int>> op;
bool flag = false;
void dfs(int x, int y,int &n)
{
    if (flag)
    {
        return;
    }
    if (cntl == n && cntr == n /*&& q.back().first == n && q.back().second == n*/)
    {
        ansq = q;
        flag = true;
        return;
    }
    if (row[x] == 1 || col[y] == 1)
    {
        return;
    }
    q.push_back({ x, y });
    row[x] = 1;
    col[y] = 1;
    cntl++;
    cntr++;
    for (int i = 0; i < 8; i++)
    {
        if (x + dirc[i][0] >= 1 && x + dirc[i][0] <= n && y + dirc[i][1] >= 1 && y + dirc[i][1] <= n)
        {
            dfs(x + dirc[i][0], y + dirc[i][1],n);
        }
    }
    row[x] = 0;
    col[y] = 0;
    cntl--;
    cntr--;
    q.pop_back();
    return;
}
void dfsnn(int x, int y, int& n)
{
    if (flag)
    {
        return;
    }
    if (cntl == n && cntr == n && q.back().first == n && q.back().second == n)
    {
        ansq = q;
        flag = true;
        return;
    }
    if (row[x] == 1 || col[y] == 1)
    {
        return;
    }
    q.push_back({ x, y });
    row[x] = 1;
    col[y] = 1;
    cntl++;
    cntr++;
    for (int i = 0; i < 8; i++)
    {
        if (x + dirc[i][0] >= 1 && x + dirc[i][0] <= n && y + dirc[i][1] >= 1 && y + dirc[i][1] <= n)
        {
            dfsnn(x + dirc[i][0], y + dirc[i][1],n);
        }
    }
    row[x] = 0;
    col[y] = 0;
    cntl--;
    cntr--;
    q.pop_back();
    return;
}
void EachT()
{
    op.push_back({ 1,3 });
    op.push_back({ 2,6 });
    op.push_back({ 5,7 });
    op.push_back({ 4,4 });
    op.push_back({ 3,1 });
    op.push_back({ 6,2 });
    op.push_back({ 7,5 });
    op.push_back({ 8,8 });
    cin >> n;
    if (n == 1) {
        cout << "POSSIBLE" << "\n" << 1 << " " << 1 << "\n";
    }
    else if (n == 2 || n == 4 || n == 3) {
        cout << "IMPOSSIBLE" << "\n";
    }
    else if (n == 5) {
        flag = false;
        dfs(1, 3,n);
        cout << "POSSIBLE" << "\n";
        for (auto i : ansq) {
            cout << i.first << " " << i.second << "\n";
        }
    }
    else
    {
        int now = n % 8;
        flag = false;
        if (now <= 5&&now!=0)now += 8;
        if (now == 0) {
            now = 8;
            dfsnn(1, 3, now);
        }
        else if (now == 6 || now == 8 || now == 12 || now == 14) {
            dfsnn(1, 3,now);
        }
        else {
            dfsnn(1, 1,now);
        }
        pair<int, int> pos;
        pos = ansq.back();
        while (pos != pair<int, int>{n, n}) {
            for (auto ok : op) {
                ansq.push_back({ pos.first + ok.first,pos.second + ok.second });
            }
            pos = ansq.back();
        }
        cout << "POSSIBLE" << "\n";
        for (auto i : ansq) {
            cout << i.first << " " << i.second << "\n";
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        EachT();
    }
    return 0;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3712kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

POSSIBLE
1 3
4 2
5 5
2 4
3 1

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5
6 6

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 0ms

memory: 3712kb

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

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 10ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 7ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 6ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 9ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 8ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 9ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 8ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 11ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 11ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 8ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 9ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 6ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 1ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 5ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 4ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 4ms

memory: 3836kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 7ms

memory: 4096kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 8ms

memory: 4096kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 6ms

memory: 3948kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 10ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 7ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 9ms

memory: 4096kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 5ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 3ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 6ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 1ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 4ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 1ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 6ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 6ms

memory: 3912kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 7ms

memory: 3980kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 7ms

memory: 4096kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 6ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 1ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 5ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 3ms

memory: 3812kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 6ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 2ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 5ms

memory: 3716kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 2ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 5ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 3ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 6ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 6ms

memory: 3752kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 2ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 5ms

memory: 4096kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 9ms

memory: 4224kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1