QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#922601#5575. Knight's Tour ReduxCharwingHawkWA 0ms3712kbC++206.7kb2025-03-01 16:18:032025-03-01 16:18:07

Judging History

This is the latest submission verdict.

  • [2025-03-01 16:18:07]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3712kb
Show
  • [2025-03-01 16:18:03]
  • Submitted

answer

#include <bits/stdc++.h> 
using namespace std;
#define int long long

//宏函数 
#define KE ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define flt(x) cout << fixed << setprecision(x);
#define all(x) (x).begin(), (x).end()
#define bcount(t) __builtin_popcount(t)
#define Mod(x,m) (((x) % m + m) % m)
#define flip(x) reverse(x)
#define lowbit(x) (x&(-x))
#define bemax(x,y) x = max(x, y)
#define bemin(x,y) x = min(x, y)
#define legal(x,lo,hi) (lo <= x && x <= hi)
#define pb push_back
#define elif else if 
#define endl '\n'

//调试部分 
#define AA cerr << "AA" << endl;
#define __ << " " <<

//常量部分 
const int N = 1e5 + 10; 
const int inf = 1e18;
const int mod = 998244353; 
typedef pair<int, int> pii;

int detx[8] = {-1, -1, -3, -3, 1, 1, 3, 3};
int dety[8] = {-3, 3, -1, 1, -3, 3, -1, 1};

int ansx[20], ansy[20];

int qx15[30] = {1, 1, 3, -1, -1, 3, 1, 1, 1, 3, 1, -3, 1, 3};
int qy15[30] = {3, 3, 1, -3, -3, 1, 3, 3, 3, 1, -3, 1, 3, 1};

int qx16[30] = {1, 3, 3, -1, -3, -1, 3, 3, 1, 1, 3, 1, -3, 1, 3};
int qy16[30] = {3, -1, -1, 3, 1, 3, -1, -1, 3, 3, 1, -3, 1, 3, 1};

int qx17[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 3, 1, -3, 1, 3};
int qy17[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 1, -3, 1, 3, 1};

int qx18[30] = {1, 1, 3, -1, -1, 3, 1, 1, 1, 3, 3, -1, -3, -1, 3, 3, 1};
int qy18[30] = {3, 3, 1, -3, -3, 1, 3, 3, 3, -1, -1, 3, 1, 3, -1, -1, 3};

int qx19[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 1, 3, -1, -1, 3, 1, 1};
int qy19[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 3, 1, -3, -3, 1, 3, 3};

int qx20[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 3, 3, -1, -3, -1, 3, 3, 1};
int qy20[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, -1, -1, 3, 1, 3, -1, -1, 3};

int qx21[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 1, 1, 3, -1, -1, 3, 1, 1, 1};
int qy21[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 3, 3, -1, -3, -3, -1, 3, 3, 3};

int qx22[30] = {1, 3, 3, -1, -3, -1, 3, 3, 1, 1, 3, 1, -3, 1, 3, 1, 3, 1, -3, 1, 3};
int qy22[30] = {3, -1, -1, 3, 1, 3, -1, -1, 3, 3, 1, -3, 1, 3, 1, 3, 1, -3, 1, 3, 1};

int qx23[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 3, 1, -3, 1, 3, 1, 3, 1, -3, 1, 3};
int qy23[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 1, -3, 1, 3, 1, 3, 1, -3, 1, 3, 1};

int qx24[30] = {1, 1, 3, -1, -1, 3, 1, 1, 1, 3, 3, -1, -3, -1, 3, 3, 1, 1, 3, 1, -3, 1, 3};
int qy24[30] = {3, 3, 1, -3, -3, 1, 3, 3, 3, -1, -1, 3, 1, 3, -1, -1, 3, 3, 1, -3, 1, 3, 1};

int qx25[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 3, 1, -3, 1, 3};
int qy25[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 3, 1, -3, -3, 1, 3, 3, 3, 1, -3, 1, 3, 1};

int qx26[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 3, 3, -1, -3, -1, 3, 3, 1, 1, 3, 1, -3, 1, 3};
int qy26[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, -1, -1, 3, 1, 3, -1, -1, 3, 3, 1, -3, 1, 3, 1};

int qx27[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 3, 1, -3, 1, 3};
int qy27[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 1, -3, 1, 3, 1};

int qx28[30] = {1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 1, 1, 3, -1, -1, 3, 1, 1, 1, 3, 3, -1, -3, -1, 3, 3, 1};
int qy28[30] = {3, 3, 3, -1, -3, -3, -1, 3, 3, 3, 3, 3, 1, -3, -3, 1, 3, 3, 3, -1, -1, 3, 1, 3, -1, -1, 3};

int visx[N], visy[N];
vector<int> ptx, pty;

bool check(int x, int y, int n){
	if(x <= 0 || x > n) return true;
	if(visx[x] == 1) return true;
	if(y <= 0 || y > n) return true;
	if(visy[y] == 1) return true;
	return false;
}

int f = 0;

void dfs(int nowx, int nowy, int st, int n){
	if(st == n){
		for(int i = 0; i < n; i++) ansx[i] = ptx[i];
		for(int i = 0; i < n; i++) ansy[i] = pty[i];
		f = 1;
		return;
	}
	for(int i = 0; i < 8; i++){
		int resx = nowx + detx[i];
		int resy = nowy + dety[i];
		if(check(resx, resy, n)) continue;
		visx[resx] = 1;
		visy[resy] = 1;
		ptx.push_back(resx);
		pty.push_back(resy);
		dfs(resx, resy, st + 1, n);
		ptx.pop_back();
		pty.pop_back();
		visx[resx] = 0;
		visy[resy] = 0;
	}
}

void solve(){
	int n; cin >> n;
	if(n <= 15){
		visx[1] = 1;
		visy[1] = 1;
		pty.push_back(1);
		ptx.push_back(1);
		dfs(1, 1, 1, n);
		
		if(f == 0) cout << "IMPOSSIBLE\n";
		else{
			cout << "POSSIBLE\n";
			for(int i = 0; i < n; i++){
				cout << ansx[i] << ' ' << ansy[i] << endl;
			} 
		}
	}
	else{
		n -= 15;
		cout << "POSSIBLE\n";
		cout << "1 1\n";
		int cnt = n / 14;
		int res = 15 + n % 14;
		int nx = 1, ny = 1;
//		cout << cnt << ' ' << res;
		for(int i = 1; i <= cnt; i++){
			for(int j = 0; j <= 13; j++){
				nx += qx15[j];
				ny += qy15[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 15){
			for(int j = 0; j <= 13; j++){
				nx += qx15[j];
				ny += qy15[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 16){
			for(int j = 0; j <= 14; j++){
				nx += qx16[j];
				ny += qy16[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 17){
			for(int j = 0; j <= 15; j++){
				nx += qx17[j];
				ny += qy17[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 18){
			for(int j = 0; j <= 16; j++){
				nx += qx18[j];
				ny += qy18[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 19){
			for(int j = 0; j <= 17; j++){
				nx += qx19[j];
				ny += qy19[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 20){
			for(int j = 0; j <= 18; j++){
				nx += qx20[j];
				ny += qy20[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 21){
			for(int j = 0; j <= 19; j++){
				nx += qx21[j];
				ny += qy21[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 22){
			for(int j = 0; j <= 20; j++){
				nx += qx22[j];
				ny += qy22[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 23){
			for(int j = 0; j <= 21; j++){
				nx += qx23[j];
				ny += qy23[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 24){
			for(int j = 0; j <= 22; j++){
				nx += qx24[j];
				ny += qy24[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 25){
			for(int j = 0; j <= 23; j++){
				nx += qx25[j];
				ny += qy25[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 26){
			for(int j = 0; j <= 24; j++){
				nx += qx26[j];
				ny += qy26[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 27){
			for(int j = 0; j <= 25; j++){
				nx += qx27[j];
				ny += qy27[j];
				cout << nx << ' ' << ny << endl;
			}
		}
		if(res == 28){
			for(int j = 0; j <= 26; j++){
				nx += qx28[j];
				ny += qy28[j];
				cout << nx << ' ' << ny << endl;
			}
		}
	}
		
}

signed main(){
    KE;
    int T = 1;
    // cin >> T;
    // flt(3);
    while(T--){
        solve();
    } 
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

1

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

2

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

3

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3712kb

input:

5

output:

IMPOSSIBLE

result:

wrong answer jury has the better answer: jans = 1, pans = 0 (1 is Possible)
English 繁體中文 简体中文

伺服器時間: 2025-04-03 23:55:04 | 開源專案