QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#82574	#5575. Knight's Tour Redux	NYCU_Yamada	AC ✓	19ms	5256kb	C++20	3.6kb	2023-02-28 06:56:15	2023-02-28 06:56:42

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-02-28 06:56:42]
Judged

Verdict: AC
Time: 19ms
Memory: 5256kb

Show

[2023-02-28 06:56:15]
Submitted

answer

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("unroll-loops", "Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define double __float80
using pii = pair<int,int>;
template <typename T> using MaxHeap = priority_queue<T>;
template <typename T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) (int)((a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define X first
#define Y second

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    template <typename ... U> Vec(int n = 0, U ... _u) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(_u...)) {}
};
template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

#ifdef local
#define debug(...) \
    fprintf(stderr, "\e[1;93mAt [%s], Line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_x) {cerr << _x << endl;}
template <typename T, typename ...S> void _do(T &&_x, S &&..._t) {cerr << _x << ", "; _do(_t...);}
#define IOS() void()
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define endl "\n"
#define debug(...) void()
#endif

template <typename U, typename V> bool chmin(U &lhs, V rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename U, typename V> bool chmax(U &lhs, V rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const vector<pii> vec[11] = {
    {{1, 1}, {2, 4}, {3, 7}, {6, 8}, {5, 5}, {4, 2}, {7, 3}, {8, 6}}, 
    {{1, 1}, {2, 4}, {3, 7}, {6, 8}, {5, 5}, {4, 2}, {7, 3}, {8, 6}, {9, 9}},
    {{1, 1}, {2, 4}, {3, 7}, {4, 10}, {7, 9}, {6, 6}, {5, 3}, {8, 2}, {9, 5}, {10, 8}},
    {{1, 1}, {2, 4}, {3, 7}, {4, 10}, {7, 9}, {6, 6}, {5, 3}, {8, 2}, {9, 5}, {10, 8}, {11, 11}},
    {{1, 1}, {2, 4}, {5, 5}, {4, 8}, {3, 11}, {6, 12}, {7, 9}, {10, 10}, {9, 7}, {12, 6}, {11, 3}, {8, 2}},
    {{1, 3}, {4, 4}, {5, 1}, {2, 2}, {3, 5}},
    {{1, 1}, {2, 4}, {5, 3}, {6, 6}, {3, 5}, {4, 2}},
    {{1, 1}, {2, 4}, {3, 7}, {6, 6}, {7, 3}, {4, 2}, {5, 5}}
};

void solve() {
    int n; cin >> n;
    if (n == 1) {
        cout << "POSSIBLE" << endl;
        cout << 1 << ' ' << 1 << endl;
        return void();
    }
    if (n <= 4) return cout << "IMPOSSIBLE" << endl, void();
    
    cout << "POSSIBLE" << endl;
    
    vector<pii> ans;
    if (n % 8 == 5) {
        for (int i = 0; i < 5; ++i) {
            ans.eb(vec[5][i].X, vec[5][i].Y);
        }
    }
    int cur = 5 * (n % 8 == 5);
    for (int i = 0; i < n / 8 - (n % 8 <= 4); ++i) {
        for (int j = 0; j < 8; ++j) {
            ans.eb(vec[0][j].X + cur, vec[0][j].Y + cur);
        }
        cur += 8;
    }
    
    if (n % 8 != 5) {
        for (auto [dx, dy] : vec[n%8]) {
            ans.eb(dx + cur, dy + cur);
        }
    }
    
    // assert(SZ(ans) == n);
    // vector<int> chkx(n+1), chky(n+1);
    // for (int i = 0; i < n-1; ++i) {
        // assert((set<int>{abs(ans[i].X - ans[i+1].X), abs(ans[i].Y - ans[i+1].Y)}) == (set<int>{1, 3}));
        // assert(chkx[ans[i].X]++ == 0);
        // assert(chky[ans[i].Y]++ == 0);
    // }
    // assert(chkx[0] == 0);
    // assert(chky[0] == 0);
    // assert(chkx[ans[n-1].X]++ == 0);
    // assert(chky[ans[n-1].Y]++ == 0);
    
    for (int i = 0; i < n; ++i) {
        cout << ans[i].X << ' ' << ans[i].Y << endl; 
    }
}

signed main(){
    IOS();
    int t = 1; // cin >> t;
    for (int i = 1; i <= t; ++i) solve();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3344kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 2ms

memory: 3380kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 2ms

memory: 3300kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 2ms

memory: 3396kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 2ms

memory: 3352kb

input:

output:

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

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 1ms

memory: 3336kb

input:

output:

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

result:

ok answer = 1

Test #8:

score: 0

Accepted

time: 2ms

memory: 3348kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 2ms

memory: 3428kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 0ms

memory: 3360kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 2ms

memory: 3340kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 2ms

memory: 3428kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 2ms

memory: 3336kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 2ms

memory: 3420kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 0ms

memory: 3412kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 2ms

memory: 3412kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 0ms

memory: 3416kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 18ms

memory: 5104kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 17ms

memory: 5100kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 11ms

memory: 5192kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 18ms

memory: 5120kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 6ms

memory: 5224kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 18ms

memory: 5196kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 8ms

memory: 5196kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 6ms

memory: 5108kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 17ms

memory: 5188kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 17ms

memory: 5184kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 17ms

memory: 5192kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 4ms

memory: 5256kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 5ms

memory: 3752kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 8ms

memory: 4172kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 3ms

memory: 3660kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 10ms

memory: 5144kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 16ms

memory: 5252kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 2ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 5ms

memory: 4176kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 17ms

memory: 5216kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 9ms

memory: 5100kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 8ms

memory: 5136kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 4ms

memory: 4204kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 2ms

memory: 3668kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 10ms

memory: 4100kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 5ms

memory: 3752kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 8ms

memory: 5152kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 0ms

memory: 3568kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 10ms

memory: 5104kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 5ms

memory: 4088kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 9ms

memory: 5220kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 9ms

memory: 5144kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 5ms

memory: 5096kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 3ms

memory: 3456kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 6ms

memory: 4144kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 10ms

memory: 4092kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 4ms

memory: 5104kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 6ms

memory: 3656kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 5ms

memory: 3564kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 9ms

memory: 4148kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 8ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 7ms

memory: 4080kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 6ms

memory: 3748kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 8ms

memory: 4164kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 10ms

memory: 4084kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 6ms

memory: 3744kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 4ms

memory: 4060kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 17ms

memory: 5104kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 19ms

memory: 5128kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 1ms

memory: 3608kb

input:

output:

result:

ok answer = 1