QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178043#7226. The Impressive Pathucup-team004TL 0ms3856kbC++201.7kb2023-09-13 17:37:362023-09-13 17:37:37

Judging History

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

  • [2023-09-13 17:37:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3856kb
  • [2023-09-13 17:37:36]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int dx[] = {-2, -1, -2, 1, -1, 2, 1, 2};
constexpr int dy[] = {-1, -2, 1, -2, 2, -1, 2, 1};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, t;
    std::cin >> n >> m >> t;
    
    std::vector vis(n, std::vector<bool>(m));
    std::vector<std::pair<int, int>> ans;
    int p[8];
    std::iota(p, p + 8, 0);
    
    while (true) {
        std::mt19937 rng;
        std::shuffle(p, p + 8, rng);
        int tot = 0;
        auto dfs = [&](auto self, int x, int y, int t) {
            tot++;
            // std::cerr << x << " " << y << " " << t << "\n";
            vis[x][y] = true;
            if (n - 1 - x > 2 * t || m - 1 - y > 2 * t || n - 1 - x + m - 1 - y > 3 * t) {
                return;
            }
            if (tot > 1E6) {
                return;
            }
            if (x == n - 1 && y == m - 1) {
                if (t == 0) {
                    for (auto [x, y] : ans) {
                        std::cout << x + 1 << " " << y + 1 << "\n";
                    }
                    std::exit(0);
                }
                return;
            }
            for (int k = 0; k < 8; k++) {
                int nx = x + dx[p[k]];
                int ny = y + dy[p[k]];
                if (0 <= nx && nx < n && 0 <= ny && ny < m && !vis[nx][ny]) {
                    ans.emplace_back(nx, ny);
                    self(self, nx, ny, t - 1);
                    ans.pop_back();
                }
            }
            vis[x][y] = false;
        };
        dfs(dfs, 0, 0, t);
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8 8 16

output:

2 3
3 1
1 2
2 4
3 2
1 3
2 1
3 3
1 4
2 2
4 1
5 3
3 4
4 6
6 7
8 8

result:

ok correct

Test #2:

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

input:

8 8 32

output:

2 3
3 1
1 2
2 4
3 2
1 3
2 1
3 3
1 4
2 2
4 1
5 3
3 4
1 5
2 7
3 5
1 6
2 8
3 6
1 7
2 5
4 4
5 2
7 1
6 3
4 2
6 1
7 3
5 4
4 6
6 7
8 8

result:

ok correct

Test #3:

score: -100
Time Limit Exceeded

input:

8 8 48

output:


result: