QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#119225	#5575. Knight's Tour Redux	hos.lyric🐇	AC ✓	12ms	4260kb	C++14	3.6kb	2023-07-05 05:59:14	2023-07-05 05:59:16

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-07-05 05:59:16]
Judged

Verdict: AC
Time: 12ms
Memory: 4260kb

Show

[2023-07-05 05:59:14]
Submitted

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr char DATA[3][12][12] = {
{
"a......",
"...b...",
"..e....",
".....f.",
"....c..",
".d.....",
"......g",
},
{
"a........",
"...b.....",
"......c..",
".f.......",
"....e....",
".......d.",
"..g......",
".....h...",
"........i",
},
{
"a..........",
"...b.......",
"......c....",
".........d.",
"..g........",
".....f.....",
"........e..",
".h.........",
"....i......",
".......j...",
"..........k",
},
};

vector<pair<int, int>> solve(int N) {
  vector<pair<int, int>> ans;
  auto add = [&](int x, int y) -> void {
    ans.emplace_back(x, y);
  };
  
  if (N == 1) {
    add(0, 0);
  } else if (N <= 4) {
    return {};
  } else {
    int n = (N == 5) ? 5 : (6 + (N - 6) % 6);
    {
      const int h = (n == 5) ? 0 : ((n - 6) / 2);
      const int l = (n == 5 || n % 2 == 0) ? 1 : 0;
      const int r = l + n;
      vector<pair<char, pair<int, int>>> ps;
      for (int x = l; x < r; ++x) for (int y = l; y < r; ++y) if (DATA[h][x][y] != '.') {
        ps.emplace_back(DATA[h][x][y], make_pair(x - l, y - l));
      }
      sort(ps.begin(), ps.end());
      for (const auto &p : ps) {
        add(p.second.first, p.second.second);
      }
    }
    {
      const int h = 0;
      const int l = 1;
      const int r = 7;
      vector<pair<char, pair<int, int>>> ps;
      for (int x = l; x < r; ++x) for (int y = l; y < r; ++y) if (DATA[h][x][y] != '.') {
        ps.emplace_back(DATA[h][x][y], make_pair(x - l, y - l));
      }
      sort(ps.begin(), ps.end());
      for (; n < N; n += 6) {
        for (const auto &p : ps) {
          add(n + p.second.first, n + p.second.second);
        }
      }
    }
  }
  
  return ans;
}

int main() {
#ifdef LOCAL
  for (int N = 1; N <= 26; ++N) {
    cerr << N << endl;
    const auto res = solve(N);
    if (!res.empty()) {
      assert((int)res.size() == N);
      vector<string> a(N, string(N, '.'));
      for (int i = 0; i < N; ++i) {
        a[res[i].first][res[i].second] = 'a' + i;
      }
      for (int x = 0; x < N; ++x) {
        cerr << a[x] << endl;
      }
    }
  }
#endif
  
  int N;
  for (; ~scanf("%d", &N); ) {
    const auto ans = solve(N);
    if (!ans.empty()) {
      puts("POSSIBLE");
      for (const auto &p : ans) {
        printf("%d %d\n", p.first + 1, p.second + 1);
      }
    } else {
      puts("IMPOSSIBLE");
    }
  }
  return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3692kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 1ms

memory: 3452kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 1ms

memory: 3384kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5
6 6

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 1ms

memory: 3652kb

input:

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7

result:

ok answer = 1

Test #8:

score: 0

Accepted

time: 1ms

memory: 3576kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 1ms

memory: 3672kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 1ms

memory: 3696kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 1ms

memory: 3652kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 1ms

memory: 3732kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 1ms

memory: 3704kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 1ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 1ms

memory: 3652kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 4ms

memory: 4084kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 12ms

memory: 4252kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 9ms

memory: 4068kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 5ms

memory: 4260kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 5ms

memory: 4216kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 12ms

memory: 4208kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 10ms

memory: 4128kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 9ms

memory: 4168kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 12ms

memory: 4160kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 7ms

memory: 4072kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 12ms

memory: 4064kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 2ms

memory: 4176kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 2ms

memory: 3804kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 2ms

memory: 3772kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 4ms

memory: 3816kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 5ms

memory: 3808kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 7ms

memory: 4084kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 5ms

memory: 4132kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 1ms

memory: 3672kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 3ms

memory: 3872kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 2ms

memory: 4196kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 9ms

memory: 4248kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 7ms

memory: 4208kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 7ms

memory: 3764kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 3ms

memory: 3712kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 6ms

memory: 4252kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 2ms

memory: 3756kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 5ms

memory: 4132kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 0ms

memory: 3856kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 9ms

memory: 4204kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 4ms

memory: 4132kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 10ms

memory: 4208kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 1ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 6ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 6ms

memory: 3868kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 9ms

memory: 4112kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 4ms

memory: 3696kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 3ms

memory: 3812kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 6ms

memory: 3832kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 5ms

memory: 3764kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 2ms

memory: 3808kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 4ms

memory: 3768kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 4ms

memory: 3816kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 7ms

memory: 3868kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 1ms

memory: 3808kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 2ms

memory: 3796kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 1ms

memory: 4244kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 8ms

memory: 4204kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 1ms

memory: 3816kb

input:

output:

result:

ok answer = 1