QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#81839	#5575. Knight's Tour Redux	whatever^#	AC ✓	27ms	3680kb	C++14	1.4kb	2023-02-26 14:37:17	2023-02-26 14:37:20

Judging History

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

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

[2023-02-26 14:37:20]
评测

测评结果：AC
用时：27ms
内存：3680kb

查看

[2023-02-26 14:37:17]
提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int dx[8] = {-3, -3, -1, -1, 1, 1, 3, 3};
constexpr int dy[8] = {-1, 1, -3, 3, -3, 3, -1, 1};
int n, ok, dt, vx[N], vy[N];
vector<pair<int, int>> P;
void dfs(int x, int y, int st) {
  if(ok) return;
  P.push_back({x, y});
  vx[x] = vy[y] = 1;
  if(st == n) {
    ok = 1;
    for(auto it : P) cout << it.first + dt << " " << it.second + dt << "\n";
  }
  else {
    for(int d = 0; d < 8; d++) {
      int xx = x + dx[d], yy = y + dy[d];
      if(xx < 1 || xx > n || yy < 1 || yy > n) continue;
      if(!vx[xx] && !vy[yy]) dfs(xx, yy, st + 1);
    }
  }
  vx[x] = vy[y] = 0;
  P.pop_back();
}

constexpr int Dx[8] = {1, 2, 3, 6, 5, 4, 7, 8};
constexpr int Dy[8] = {1, 4, 7, 8, 5, 2, 3, 6};
int main() {
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n;
  if(n == 2 || n == 3 || n == 4) cout << "IMPOSSIBLE\n", exit(0);
  cout << "POSSIBLE\n";
  while(n > 15) {
    for(int d = 0; d < 8; d++)
      cout << dt + Dx[d] << " " << dt + Dy[d] << "\n";
    dt += 8, n -= 8;
  }
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      if(!ok) dfs(i, j, 1);
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
/*
g++ J.cpp -o J -std=c++14 -O2 -DALEX_WEI
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3556kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 2ms

memory: 3184kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 1ms

memory: 3308kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 2ms

memory: 3236kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

POSSIBLE
1 3
4 2
5 5
2 4
3 1

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 2ms

memory: 3676kb

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

memory: 3528kb

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

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 2ms

memory: 3680kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 2ms

memory: 3536kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 1ms

memory: 3580kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 2ms

memory: 3592kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 2ms

memory: 3680kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 2ms

memory: 3676kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 2ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 2ms

memory: 3492kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 2ms

memory: 3536kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 0ms

memory: 3532kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 2ms

memory: 3584kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 2ms

memory: 3596kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 15ms

memory: 3632kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 12ms

memory: 3592kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 9ms

memory: 3676kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 20ms

memory: 3672kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 10ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 20ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 17ms

memory: 3500kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 19ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 13ms

memory: 3628kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 15ms

memory: 3564kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 6ms

memory: 3668kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 17ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 6ms

memory: 3500kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 6ms

memory: 3540kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 5ms

memory: 3564kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 8ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 17ms

memory: 3540kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 17ms

memory: 3528kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 11ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 6ms

memory: 3676kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 9ms

memory: 3620kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 15ms

memory: 3680kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 10ms

memory: 3560kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 7ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 11ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 3ms

memory: 3500kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 18ms

memory: 3632kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 15ms

memory: 3584kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 5ms

memory: 3532kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 4ms

memory: 3680kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 3ms

memory: 3624kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 14ms

memory: 3624kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 4ms

memory: 3672kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 14ms

memory: 3524kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 6ms

memory: 3592kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 9ms

memory: 3588kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 6ms

memory: 3532kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 4ms

memory: 3584kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 7ms

memory: 3512kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 8ms

memory: 3496kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 3ms

memory: 3620kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 7ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 13ms

memory: 3612kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 5ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 6ms

memory: 3672kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 7ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 27ms

memory: 3612kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 27ms

memory: 3632kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok answer = 1