QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#903704	#5575. Knight's Tour Redux	juruoA	AC ✓	9ms	3840kb	C++11	2.5kb	2025-02-17 16:58:59	2025-02-17 16:59:09

Judging History

This is the latest submission verdict.

[2025-02-17 16:59:09]
Judged

Verdict: AC
Time: 9ms
Memory: 3840kb

Show

[2025-02-17 16:58:59]
Submitted

answer

#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf;

inline li read(){
	li ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 

vector<pair<li, li>> v;
li vis1[1010], vis2[1010], fl = 0;
li xx[2020], yy[2020];
li dx[] = {-1, -1, 1, 1, 3, 3, -3, -3};
li n;
li dy[] = {3, -3, 3, -3, 1, -1, 1, -1};

void dfs(li x, li y, li step, li add){
    // cout << x << " " << y << " " << step << endl;
    xx[step] = x, yy[step] = y;
    vis1[x] = 1, vis2[y] = 1;
    if(step == n){
        for(li i = 1; i <= n; i++) printf("%lld %lld\n", xx[i] + add, yy[i] + add);
        exit(0);
    }
    for(li i = 0; i < 8; i++){
        li tx = x + dx[i], ty = y + dy[i];
        if(0 >= tx || 0 >= ty || tx > n || ty > n) continue;
        if(vis1[tx] || vis2[ty]) continue;
        dfs(tx, ty, step + 1, add);
    }
    vis1[x] = 0, vis2[y] = 0;
}

int main(){
    // freopen("wonderful.ans", "r", stdin);
    // freopen("www.ww", "w", stdout); 
	n = read();
    v.push_back({1, 1});
    v.push_back({2, 4});
    v.push_back({5, 5});
    v.push_back({6, 2});
    v.push_back({3, 3});
    v.push_back({4, 6});
    if(n <= 6){
        if(n == 1){
            printf("POSSIBLE\n1 1\n");
        } else if(n == 5){
            printf("POSSIBLE\n1 3\n4 4\n5 1\n2 2\n3 5\n");
        } else if(n == 6){
            printf("POSSIBLE\n1 1\n2 4\n5 5\n6 2\n3 3\n4 6\n");
        } else puts("IMPOSSIBLE");
    } else{
        printf("POSSIBLE\n");
        li add = 0;
        while(n >= 12){
            for(auto x : v) printf("%lld %lld\n", x.first + add, x.second + add);
            add += 6;
            n -= 6;
        }
        for(li i = 1; i <= n; i++){
            for(li j = 1; j <= n; j++){
                dfs(i, j, 1, add);
            }
        }
    }
    return 0;
}

源文件, 语言: C++11

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3712kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3712kb

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

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

memory: 3840kb

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

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 0ms

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

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 7ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 8ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 8ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 8ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 8ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 6ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 7ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 9ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 6ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 7ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 8ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 6ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 2ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 3ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 5ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 6ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 3ms

memory: 3712kb

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

memory: 3712kb

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

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 2ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 5ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 2ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 5ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 5ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 5ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 7ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 8ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 4ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 4ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 3ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 4ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 2ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 2ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 3ms

memory: 3840kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 4ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 2ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 4ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 2ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 6ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 8ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok answer = 1