QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#81838#5575. Knight's Tour Reduxwhatever#RE 2ms3532kbC++141.3kb2023-02-26 14:34:012023-02-26 14:34:18

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-26 14:34:18]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 3532kb
  • [2023-02-26 14:34:01]
  • Submitted

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;
  }
  dfs(1, 1, 1);
  assert(ok);
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
/*
g++ J.cpp -o J -std=c++14 -O2 -DALEX_WEI
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3532kb

input:

1

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 2ms
memory: 3264kb

input:

2

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

3

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

4

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: -100
Dangerous Syscalls

input:

5

output:


result: