QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#338196	#5575. Knight's Tour Redux	ucup-team1198^#	AC ✓	11ms	5176kb	C++20	2.7kb	2024-02-25 18:57:01	2024-02-25 18:57:01

Judging History

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

[2024-02-25 18:57:01]
评测

测评结果：AC
用时：11ms
内存：5176kb

查看

[2024-02-25 18:57:01]
提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<array<int, 2>> get0 = {},
                      get1 = {{0, 0}},
                      get8 = {{0, 0}, {1, 3}, {2, 6}, {5, 7}, {6, 4}, {3, 5}, {4, 2}, {7, 1}},
                      get10= {{0, 0}, {3, 1}, {6, 2}, {9, 3}, {8, 6}, {7, 9}, {4, 8}, {1, 7}, {2, 4}, {5, 5}},
                      get5 = {{2, 0}, {3, 3}, {0, 4}, {1, 1}, {4, 2}};

void print(vector<array<int, 2>> a) {
    /// set<int> xs, ys;
    for (auto elem : a) {
        cout << elem[0] + 1 << " " << elem[1] + 1 << "\n";
        /// xs.insert(elem[0]);
        /// ys.insert(elem[1]);
    }
    /**assert(xs.size() == a.size() && ys.size() == a.size());
    for (int i = 1; i < (int)a.size(); ++i) {
        int dx = abs(a[i][0] - a[i - 1][0]);
        int dy = abs(a[i][1] - a[i - 1][1]);
        assert(min(dx, dy) == 1 && max(dx, dy) == 3);
    }*/
}

void solve(vector<array<int, 2>> s, vector<array<int, 2>> t, int k) {
    vector<array<int, 2>> res;
    reverse(s.begin(), s.end());
    for (auto& elem : s) {
        elem[0] = s.size() - 1 - elem[0];
        elem[1] = s.size() - 1 - elem[1];
    }
    int d = 0;

    auto add = [&](vector<array<int, 2>> a) {
        for (auto elem : a) {
            res.push_back({elem[0] + d, elem[1] + d});
        }
        d += a.size();
    };

    add(s);
    if (k == -1) {
        res.pop_back();
        --d;
    }
    for (int i = 0; i < k; ++i) {
        add(get5);
        add(get1);
    }
    if (k >= 0) {
        add(get5);
    }
    add(t);
    print(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    if (n == 2 || n == 3 || n == 4) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    cout << "POSSIBLE\n";
    if (n == 9) {
        for (int i = 1; i <= 9; ++i) {
            cout << get10[i][0] << " " << get10[i][1] << "\n";
        }
        return 0;
    }
    int r = n % 6;
    if (r == 0) {
        solve(get0, get1, (n - 6) / 6);
    } else if (r == 1) {
        solve(get1, get1, (n - 7) / 6);
    } else if (r == 2) {
        solve(get1, get8, (n - 14) / 6);
    } else if (r == 3) {
        solve(get0, get10, (n - 15) / 6);
    } else if (r == 4) {
        solve(get1, get10, (n - 16) / 6);
    } else {
        solve(get0, get0, (n - 5) / 6);
    }
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3604kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 0ms

memory: 3756kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 0ms

memory: 3832kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

POSSIBLE
3 1
4 4
1 5
2 2
5 3

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

output:

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

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 0ms

memory: 3824kb

input:

output:

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

result:

ok answer = 1

Test #8:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 0ms

memory: 3760kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 0ms

memory: 3552kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 10ms

memory: 5056kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 10ms

memory: 5176kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 11ms

memory: 5072kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 11ms

memory: 4976kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 7ms

memory: 5068kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 5ms

memory: 4980kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 5ms

memory: 4964kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 10ms

memory: 5004kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 10ms

memory: 5008kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 3ms

memory: 5124kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 5ms

memory: 4972kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 8ms

memory: 4436kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 3ms

memory: 4004kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 5ms

memory: 3952kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 4ms

memory: 3780kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 4ms

memory: 3904kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 5ms

memory: 4504kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 9ms

memory: 4860kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 3ms

memory: 4240kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 11ms

memory: 4736kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 8ms

memory: 4436kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 9ms

memory: 4876kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 7ms

memory: 4396kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 4ms

memory: 3792kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 6ms

memory: 4388kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 2ms

memory: 3748kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 4ms

memory: 4452kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 1ms

memory: 3948kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 8ms

memory: 4596kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 3ms

memory: 4268kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 8ms

memory: 4476kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 6ms

memory: 4736kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 8ms

memory: 4428kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 6ms

memory: 4196kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 5ms

memory: 3924kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 4ms

memory: 4648kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 3ms

memory: 3940kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 2ms

memory: 3668kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 5ms

memory: 3972kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 4ms

memory: 4004kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 5ms

memory: 4268kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 3ms

memory: 3808kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 6ms

memory: 4236kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 6ms

memory: 4248kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 3ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 4ms

memory: 3972kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 9ms

memory: 4700kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 10ms

memory: 5024kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 1ms

memory: 3716kb

input:

output:

result:

ok answer = 1