QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#593800	#5575. Knight's Tour Redux	Trynitas (Ioan Popescu, Toma Ariciu)^#	AC ✓	18ms	4284kb	C++14	3.0kb	2024-09-27 16:06:24	2024-09-27 16:06:25

Judging History

This is the latest submission verdict.

[2024-09-27 16:06:25]
Judged

Verdict: AC
Time: 18ms
Memory: 4284kb

Show

[2024-09-27 16:06:24]
Submitted

answer

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <random>
#include <ctime>
#include <cstdlib>
#include <chrono>

using namespace std;

const int dx[] = {1, 3};
const int dy[] = {3, 1};

int n;
int viz[100][100];
int fx[100], fy[100];

vector<pair<int, int>> trace;
int back(int i, int j, bool res = true, int nr = 1) {
  if (nr == n && (res || (i == n && j == n))) {
    return 1;
  }

  if (nr == n) {
    return 0;
  }

  for (int k = 0; k < 2; ++k) {
    for (int sx = -1; sx <= 1; sx += 2) {
      for (int sy = -1; sy <= 1; sy += 2) {
        int x = dx[k] * sx + i;
        int y = dy[k] * sy + j;

        if (x < 1 || y < 1 || x > n || y > n || fx[x] || fy[y]) {
          continue;
        }
        fx[x] = 1;
        fy[y] = 1;
        viz[x][y] = nr + 1;
        trace.push_back({x, y});
        int f = back(x, y, res, nr + 1);
        viz[x][y] = 0;
        fx[x] = 0;
        fy[y] = 0;
        if (f) {
          return 1;
        }
        trace.pop_back();
      }
    }
  }

  return 0;
}

void solve() {
  auto get_trace = [&](int x, bool res) {
    n = x;
    for (int i = 1; i <= 3; ++i) {
      for (int j = 1; j <= 3; ++j) {
        if (i > n || j > n) {
          return std::vector<pair<int, int>>();
        }

        if (!(res || (i == 1 && j == 1))) {
          return trace;
        }

        fx[i] = 1;
        fy[j] = 1;
        viz[i][j] = 1;
        trace.push_back({i, j});
        int f = back(i, j, res);
        viz[i][j] = 0;
        fx[i] = 0;
        fy[j] = 0;
        if (f) {
          auto res = trace;
          trace.clear();
          return res;
        }
        trace.pop_back();
      }
    }

    return std::vector<pair<int, int>>();
  };

  int N;
  cin >> N;

  if (N <= 13) {
    auto ans = get_trace(N, true);

    if (ans.empty()) {
      cout << "IMPOSSIBLE\n";
      return;
    }
    cout << "POSSIBLE\n";
    for (auto it : ans) {
      cout << it.first << " " << it.second << "\n";
    }
    return;
  } else {
    vector<pair<int, int>> ans;
    int off = 0;
    while (N >= 13) {
      N -= 6;
      auto tmp = get_trace(7, false);
      if (ans.empty()) {
        ans = tmp;
      } else {
        tmp.erase(tmp.begin());
        for (auto it : tmp) {
          ans.push_back({it.first + off, it.second + off});
        }
      }
      off += 6;
    }

    auto tmp = get_trace(N, true); 
    tmp.erase(tmp.begin());
    for (auto it : tmp) {
      ans.push_back({it.first + off, it.second + off});
    }

    cout << "POSSIBLE\n";
    for (auto it : ans) {
      cout << it.first << " " << it.second << "\n";
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;
  while (t--)
    solve();

  return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3608kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

output:

POSSIBLE
1 3
4 2
5 5
2 4
3 1

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 0ms

memory: 3564kb

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

memory: 3672kb

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

memory: 3628kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 0ms

memory: 3504kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 0ms

memory: 3868kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 0ms

memory: 3832kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 17ms

memory: 4284kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 13ms

memory: 4152kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 17ms

memory: 4280kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 17ms

memory: 4200kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 17ms

memory: 4176kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 17ms

memory: 4048kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 17ms

memory: 4088kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 14ms

memory: 4108kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 17ms

memory: 4052kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 17ms

memory: 4080kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 17ms

memory: 4272kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 13ms

memory: 4284kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 5ms

memory: 3696kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 7ms

memory: 3748kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 6ms

memory: 3728kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 7ms

memory: 3964kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 14ms

memory: 4284kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 12ms

memory: 4120kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 1ms

memory: 3604kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 10ms

memory: 3800kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 12ms

memory: 4052kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 14ms

memory: 4112kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 11ms

memory: 4124kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 11ms

memory: 4104kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 9ms

memory: 3688kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 4ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 14ms

memory: 4168kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 2ms

memory: 3684kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 13ms

memory: 4120kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 11ms

memory: 4200kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 10ms

memory: 4076kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 12ms

memory: 4100kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 13ms

memory: 4272kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 10ms

memory: 3756kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 8ms

memory: 3732kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 12ms

memory: 4284kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 3ms

memory: 3696kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 8ms

memory: 3928kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 6ms

memory: 3800kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 9ms

memory: 3736kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 6ms

memory: 3700kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 10ms

memory: 3968kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 9ms

memory: 4008kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 6ms

memory: 3760kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 12ms

memory: 4120kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 18ms

memory: 4092kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 1ms

memory: 3748kb

input:

output:

result:

ok answer = 1