#include "coprobber.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;
int strategy;
int n;
vector <int> ve[MAX_N];
int D[MAX_N], F[MAX_N];
int disc = -1;
int P, W, H;
void rek(int x, int p) {
D[x] = ++disc;
for (int y : ve[x]) {
if (y == p) continue;
rek(y, x);
}
F[x] = disc;
return;
}
int start(int N, bool A[MAX_N][MAX_N]) {
n = N;
int e = 0;
REP(i, n) {
REP(j, n) {
if (A[i][j]) ve[i].push_back(j), e++;
}
}
e /= 2;
if (e == n - 1) {
rek(0, 0);
strategy = 0, P = 0;
return 0;
}
W = 1, H = 1;
while (A[W - 1][W] == 1) W++;
H = n / W;
assert(H * W == n);
strategy = 1, P = 0;
return 0;
}
int nextMove(int R) {
if (strategy == 0) {
for (int x : ve[P]) {
if (D[x] < D[P]) continue;
if (D[x] <= D[R] && F[R] <= F[x]) {
P = x;
return P;
}
}
assert(0);
} else if (strategy == 1) {
if (abs((R % W) - (P % W)) == 1 && abs((R / W) - (P / W)) == 1) return P;
if (R % W == P % W) {
if (R > P) P += W;
else P -= W;
return P;
} else if (abs((R % W) - (P % W)) == 1) {
if (R / W == P / W) {
if (R > P) P++;
else P--;
return P;
} else {
if (R > P) P += W;
else P -= W;
return P;
}
} else {
if (R % W > P % W) P++;
else P--;
return P;
}
} else {
assert(0);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
43 ms |
1912 KB |
Output is correct |
5 |
Correct |
12 ms |
1024 KB |
Output is correct |
6 |
Correct |
44 ms |
1592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
41 ms |
1656 KB |
Output is correct |
4 |
Correct |
43 ms |
1784 KB |
Output is correct |
5 |
Correct |
39 ms |
1656 KB |
Output is correct |
6 |
Correct |
41 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Incorrect |
2 ms |
384 KB |
Cop cannot catch the robber, but start() did not return -1 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
480 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
44 ms |
1784 KB |
Output is correct |
5 |
Correct |
12 ms |
1024 KB |
Output is correct |
6 |
Correct |
45 ms |
1656 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
42 ms |
1656 KB |
Output is correct |
10 |
Correct |
51 ms |
1912 KB |
Output is correct |
11 |
Correct |
40 ms |
1656 KB |
Output is correct |
12 |
Correct |
42 ms |
1656 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Incorrect |
2 ms |
384 KB |
Cop cannot catch the robber, but start() did not return -1 |
15 |
Halted |
0 ms |
0 KB |
- |