QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#125497	#5575. Knight's Tour Redux	KKT89	AC ✓	12ms	4276kb	C++17	5.8kb	2023-07-16 19:13:57	2023-07-16 19:13:58

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-16 19:13:58]
Judged

Verdict: AC
Time: 12ms
Memory: 4276kb

Show

[2023-07-16 19:13:57]
Submitted

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    if(n == 1){
        cout << "POSSIBLE\n";
        cout << 1 << " " << 1 << "\n";
    }
    else if(n <= 4){
        cout << "IMPOSSIBLE\n";
    }
    else{
        cout << "POSSIBLE\n";
        if(n == 5){
            cout << 1 << " " << 3 << "\n";
            cout << 4 << " " << 4 << "\n";
            cout << 5 << " " << 1 << "\n";
            cout << 2 << " " << 2 << "\n";
            cout << 3 << " " << 5 << "\n";
        }
        else if(n == 6){
            cout << 1 << " " << 2 << "\n";
            cout << 2 << " " << 5 << "\n";
            cout << 5 << " " << 6 << "\n";
            cout << 6 << " " << 3 << "\n";
            cout << 3 << " " << 4 << "\n";
            cout << 4 << " " << 1 << "\n";
        }
        else{
            // resの中身は0-indexedで書く
            auto solve = [&](auto solve,int n)->vector<pair<int,int>>{
                vector<pair<int,int>> res;
                if(n%6 == 1){
                    res.push_back({0,0});
                    int x = 0, y = 0;
                    for (int i = 0; i < n/6; ++i) {
                        res.push_back({x+3,y+1});
                        res.push_back({x+4,y+4});
                        res.push_back({x+1,y+5});
                        res.push_back({x+2,y+2});
                        res.push_back({x+5,y+3});
                        res.push_back({x+6,y+6});
                        x += 6, y += 6;
                    }
                }
                else if(n%6 == 2){
                    res = solve(solve,n+1);
                    res.pop_back();
                }
                else if(n%6 == 5){
                    res = solve(solve,n+1);
                    res.pop_back();
                }
                else if(n%6 == 0){
                    res.push_back({0,2});
                    res.push_back({3,3});
                    res.push_back({4,0});
                    res.push_back({1,1});
                    res.push_back({2,4});
                    res.push_back({5,5});
                    int x = 5, y = 5;
                    for (int i = 0; i < n/6-1; ++i) {
                        res.push_back({x+3,y+1});
                        res.push_back({x+4,y+4});
                        res.push_back({x+1,y+5});
                        res.push_back({x+2,y+2});
                        res.push_back({x+5,y+3});
                        res.push_back({x+6,y+6});
                        x += 6, y += 6;
                    }
                }
                else if(n%6 == 3){
                    res.push_back({0,0});
                    res.push_back({3,1});
                    res.push_back({6,2});
                    res.push_back({7,5});
                    res.push_back({4,4});
                    res.push_back({1,3});
                    res.push_back({2,6});
                    res.push_back({5,7});
                    res.push_back({8,8});
                    int x = 8, y = 8;
                    for (int i = 0; i < n/6-1; ++i) {
                        res.push_back({x+3,y+1});
                        res.push_back({x+4,y+4});
                        res.push_back({x+1,y+5});
                        res.push_back({x+2,y+2});
                        res.push_back({x+5,y+3});
                        res.push_back({x+6,y+6});
                        x += 6, y += 6;
                    }
                }
                else if(n%6 == 4){
                    res.push_back({0,0});
                    res.push_back({3,1});
                    res.push_back({6,2});
                    res.push_back({9,3});
                    res.push_back({8,6});
                    res.push_back({7,9});
                    res.push_back({4,8});
                    res.push_back({1,7});
                    res.push_back({2,4});
                    res.push_back({5,5});
                    for (int i = 0; i < res.size(); ++i) {
                        res[i].first = 9-res[i].first;
                        res[i].second = 9-res[i].second;
                    }
                    reverse(res.begin(), res.end());
                    int x = 9, y = 9;
                    for (int i = 0; i < n/6-1; ++i) {
                        res.push_back({x+3,y+1});
                        res.push_back({x+4,y+4});
                        res.push_back({x+1,y+5});
                        res.push_back({x+2,y+2});
                        res.push_back({x+5,y+3});
                        res.push_back({x+6,y+6});
                        x += 6, y += 6;
                    }
                }
                return res;
            };

            auto res = solve(solve,n);

            auto check = [&]()->bool{
                vector<bool> h(n),w(n);
                if(res.size() != n) return false;
                for (int i = 0; i < n; ++i) {
                    auto [x,y] = res[i];
                    if(h[x] or w[y]) return false;
                    h[x] = true; w[y] = true;
                    if(i){
                        auto [px,py] = res[i-1];
                        int dx = abs(x-px);
                        int dy = abs(y-py);
                        if(dx > dy) swap(dx,dy);
                        if(dx != 1 or dy != 3) return false;
                    }
                }
                return true;
            };
            assert(check());
            for (int i = 0; i < res.size(); ++i) {
                cout << res[i].first+1 << " " << res[i].second+1 << "\n";
            }
        }
    }
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3504kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 1ms

memory: 3500kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 1ms

memory: 3512kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 1ms

memory: 3488kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 1ms

memory: 3488kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 0ms

memory: 3432kb

input:

output:

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

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 1ms

memory: 3444kb

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: 1ms

memory: 3472kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 1ms

memory: 3400kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 1ms

memory: 3416kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 1ms

memory: 3544kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 1ms

memory: 3496kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 1ms

memory: 3396kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 1ms

memory: 3508kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 1ms

memory: 3400kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 1ms

memory: 3452kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 1ms

memory: 3428kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 0ms

memory: 3516kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 1ms

memory: 3452kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 12ms

memory: 4164kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 6ms

memory: 4188kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 8ms

memory: 4192kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 4ms

memory: 4220kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 7ms

memory: 4192kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 8ms

memory: 4196kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 2ms

memory: 4164kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 8ms

memory: 4208kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 9ms

memory: 4180kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 12ms

memory: 4196kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 6ms

memory: 4200kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 4ms

memory: 4184kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 4ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 6ms

memory: 3832kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 4ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 6ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 4ms

memory: 4276kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 11ms

memory: 4168kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 1ms

memory: 3460kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 3ms

memory: 3884kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 12ms

memory: 4180kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 3ms

memory: 4180kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 3ms

memory: 4196kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 3ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 7ms

memory: 3796kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 3ms

memory: 3624kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 10ms

memory: 4176kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 2ms

memory: 3588kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 9ms

memory: 4220kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 4ms

memory: 3808kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 7ms

memory: 4184kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 11ms

memory: 4204kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 4ms

memory: 4216kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 3ms

memory: 3764kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 3ms

memory: 3816kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 9ms

memory: 4160kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 4ms

memory: 3536kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 0ms

memory: 3528kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 6ms

memory: 3792kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 5ms

memory: 3816kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 7ms

memory: 3836kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 4ms

memory: 3580kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 7ms

memory: 3792kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 4ms

memory: 3796kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 4ms

memory: 3600kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 5ms

memory: 3824kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 11ms

memory: 4180kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 11ms

memory: 4212kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 2ms

memory: 3656kb

input:

output:

result:

ok answer = 1