QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178043 | #7226. The Impressive Path | ucup-team004 | TL | 0ms | 3856kb | C++20 | 1.7kb | 2023-09-13 17:37:36 | 2023-09-13 17:37:37 |
Judging History
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