#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
int posc;
//const int MAX_N = 500;
vi choice[MAX_N+1][MAX_N+1][3];
int start(int N, bool A[MAX_N][MAX_N]) {
int ct[MAX_N+1][MAX_N+1][3], win[MAX_N+1][MAX_N+1][3];
vi deg(N);
for_(i, 0, N) for_(j, 0, N) if (A[i][j]) deg[i] += 1;
queue<vi> q; // {0, 0, 0 -> cop / 1 -> robber}
for_(i, 0, N) {
win[i][i][0] = win[i][i][1] = true;
q.push({i, i, 0});
q.push({i, i, 1});
}
while (q.size()) {
vi curr = q.front(); q.pop();
if (curr[2] == 0) {
for_(i, 0, N) if (A[i][curr[1]] and !win[curr[0]][i][1]) {
ct[curr[0]][i][1] += 1;
if (ct[curr[0]][i][1] == deg[i]) {
win[curr[0]][i][1] = true;
choice[curr[0]][i][1] = curr;
q.push({curr[0], i, 1});
}
}
} else {
for_(i, 0, N) if ((A[i][curr[0]] or i == curr[0]) and !win[i][curr[1]][0]) {
win[i][curr[1]][0] = true;
choice[i][curr[1]][0] = curr;
q.push({i, curr[1], 0});
}
}
}
posc = -1;
for_(i, 0, N) {
int c = 0;
for_(j, 0, N) c += win[i][j][0];
if (c == N) {
posc = i;
//cout << "can start at " << i << endl;
}
}
return posc;
}
int nextMove(int R) {
//cout << posc << " " << R << endl;
posc = choice[posc][R][0][0];
return posc;
}
//int main() {
//#ifndef ONLINE_JUDGE
//freopen("test.in", "r", stdin);
//#endif
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//bool A[MAX_N][MAX_N] = {{0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}};
//cout << start(4, A) << endl;
//cout << nextMove(1) << endl;
//cout << nextMove(0) << endl;
//return 0;
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
18048 KB |
Output is correct |
2 |
Correct |
12 ms |
18048 KB |
Output is correct |
3 |
Correct |
13 ms |
18048 KB |
Output is correct |
4 |
Correct |
594 ms |
41080 KB |
Output is correct |
5 |
Correct |
107 ms |
25336 KB |
Output is correct |
6 |
Correct |
716 ms |
41184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
18048 KB |
Output is correct |
2 |
Correct |
12 ms |
18176 KB |
Output is correct |
3 |
Correct |
622 ms |
40440 KB |
Output is correct |
4 |
Correct |
603 ms |
41080 KB |
Output is correct |
5 |
Correct |
624 ms |
39928 KB |
Output is correct |
6 |
Correct |
637 ms |
40696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
18048 KB |
Output is correct |
2 |
Correct |
12 ms |
18048 KB |
Output is correct |
3 |
Correct |
12 ms |
18048 KB |
Output is correct |
4 |
Correct |
12 ms |
18048 KB |
Output is correct |
5 |
Correct |
12 ms |
18176 KB |
Output is correct |
6 |
Correct |
13 ms |
18048 KB |
Output is correct |
7 |
Correct |
12 ms |
18048 KB |
Output is correct |
8 |
Correct |
12 ms |
18176 KB |
Output is correct |
9 |
Correct |
13 ms |
18176 KB |
Output is correct |
10 |
Correct |
15 ms |
19072 KB |
Output is correct |
11 |
Correct |
17 ms |
19456 KB |
Output is correct |
12 |
Correct |
12 ms |
18304 KB |
Output is correct |
13 |
Correct |
14 ms |
18816 KB |
Output is correct |
14 |
Correct |
20 ms |
19328 KB |
Output is correct |
15 |
Correct |
15 ms |
18816 KB |
Output is correct |
16 |
Correct |
15 ms |
18888 KB |
Output is correct |
17 |
Correct |
31 ms |
20224 KB |
Output is correct |
18 |
Correct |
14 ms |
18944 KB |
Output is correct |
19 |
Correct |
12 ms |
18048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
18048 KB |
Output is correct |
2 |
Correct |
12 ms |
18048 KB |
Output is correct |
3 |
Correct |
13 ms |
18048 KB |
Output is correct |
4 |
Correct |
594 ms |
41080 KB |
Output is correct |
5 |
Correct |
107 ms |
25336 KB |
Output is correct |
6 |
Correct |
716 ms |
41184 KB |
Output is correct |
7 |
Correct |
12 ms |
18048 KB |
Output is correct |
8 |
Correct |
12 ms |
18176 KB |
Output is correct |
9 |
Correct |
622 ms |
40440 KB |
Output is correct |
10 |
Correct |
603 ms |
41080 KB |
Output is correct |
11 |
Correct |
624 ms |
39928 KB |
Output is correct |
12 |
Correct |
637 ms |
40696 KB |
Output is correct |
13 |
Correct |
12 ms |
18048 KB |
Output is correct |
14 |
Correct |
12 ms |
18048 KB |
Output is correct |
15 |
Correct |
12 ms |
18048 KB |
Output is correct |
16 |
Correct |
12 ms |
18048 KB |
Output is correct |
17 |
Correct |
12 ms |
18176 KB |
Output is correct |
18 |
Correct |
13 ms |
18048 KB |
Output is correct |
19 |
Correct |
12 ms |
18048 KB |
Output is correct |
20 |
Correct |
12 ms |
18176 KB |
Output is correct |
21 |
Correct |
13 ms |
18176 KB |
Output is correct |
22 |
Correct |
15 ms |
19072 KB |
Output is correct |
23 |
Correct |
17 ms |
19456 KB |
Output is correct |
24 |
Correct |
12 ms |
18304 KB |
Output is correct |
25 |
Correct |
14 ms |
18816 KB |
Output is correct |
26 |
Correct |
20 ms |
19328 KB |
Output is correct |
27 |
Correct |
15 ms |
18816 KB |
Output is correct |
28 |
Correct |
15 ms |
18888 KB |
Output is correct |
29 |
Correct |
31 ms |
20224 KB |
Output is correct |
30 |
Correct |
14 ms |
18944 KB |
Output is correct |
31 |
Correct |
12 ms |
18048 KB |
Output is correct |
32 |
Correct |
12 ms |
18048 KB |
Output is correct |
33 |
Correct |
13 ms |
18048 KB |
Output is correct |
34 |
Correct |
12 ms |
18048 KB |
Output is correct |
35 |
Correct |
597 ms |
41080 KB |
Output is correct |
36 |
Correct |
106 ms |
25336 KB |
Output is correct |
37 |
Correct |
728 ms |
41112 KB |
Output is correct |
38 |
Correct |
12 ms |
18048 KB |
Output is correct |
39 |
Correct |
12 ms |
18176 KB |
Output is correct |
40 |
Correct |
632 ms |
40444 KB |
Output is correct |
41 |
Correct |
592 ms |
41080 KB |
Output is correct |
42 |
Correct |
626 ms |
39800 KB |
Output is correct |
43 |
Correct |
628 ms |
40940 KB |
Output is correct |
44 |
Correct |
12 ms |
18048 KB |
Output is correct |
45 |
Correct |
12 ms |
18048 KB |
Output is correct |
46 |
Correct |
11 ms |
18176 KB |
Output is correct |
47 |
Correct |
12 ms |
18176 KB |
Output is correct |
48 |
Correct |
15 ms |
19072 KB |
Output is correct |
49 |
Correct |
18 ms |
19456 KB |
Output is correct |
50 |
Correct |
13 ms |
18304 KB |
Output is correct |
51 |
Correct |
14 ms |
18816 KB |
Output is correct |
52 |
Correct |
18 ms |
19328 KB |
Output is correct |
53 |
Correct |
14 ms |
18816 KB |
Output is correct |
54 |
Correct |
15 ms |
18816 KB |
Output is correct |
55 |
Correct |
26 ms |
20216 KB |
Output is correct |
56 |
Correct |
13 ms |
18944 KB |
Output is correct |
57 |
Correct |
19 ms |
20608 KB |
Output is correct |
58 |
Correct |
33 ms |
23040 KB |
Output is correct |
59 |
Correct |
60 ms |
24568 KB |
Output is correct |
60 |
Correct |
1475 ms |
54688 KB |
Output is correct |
61 |
Correct |
229 ms |
30456 KB |
Output is correct |
62 |
Correct |
233 ms |
30200 KB |
Output is correct |
63 |
Correct |
1213 ms |
44040 KB |
Output is correct |
64 |
Correct |
234 ms |
29944 KB |
Output is correct |
65 |
Correct |
1332 ms |
53896 KB |
Output is correct |
66 |
Correct |
709 ms |
41144 KB |
Output is correct |
67 |
Correct |
1195 ms |
46764 KB |
Output is correct |
68 |
Correct |
550 ms |
32116 KB |
Output is correct |
69 |
Correct |
11 ms |
18048 KB |
Output is correct |