#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500;
const int M = 2 * maxN * maxN;
vector<int> g[maxN];
int good[M];
unsigned int d[M];
int siz[M];
int pos[M];
//0 if it's officer's turn, 1 if robber's one
int enc(int officerPos, int robberPos, int whoseTurn) {
return whoseTurn * maxN * maxN + officerPos * maxN + robberPos;
}
inline void expand(int cur) {
//cout << cur % (maxN * maxN) / maxN << " " << cur % maxN << " " << cur / (maxN * maxN) << siz[cur] << " " << d[cur] << endl;
assert(d[cur] <= siz[cur]);
if (d[cur] == siz[cur] || (cur / (maxN * maxN) == 0 && d[cur]))
good[cur] = pos[cur];
if (good[cur] != -1) {
assert(good[cur] == -2 || good[good[cur]] != -1);
int officerPos = cur % (maxN * maxN) / maxN;
int robberPos = cur % maxN;
if (cur / (maxN * maxN)) { //robber's turn
int j = enc(officerPos, robberPos, 0);
if (good[j] == -1 && officerPos != robberPos) {
d[j]++;
pos[j] = cur;
expand(j);
}
for (int i : g[officerPos]) {
j = enc(i, robberPos, 0);
if (good[j] == -1 && i != robberPos) {
d[j]++;
pos[j] = cur;
expand(j);
}
}
} else { //officer's turn
for (int i : g[robberPos]) {
int j = enc(officerPos, i, 1);
if (good[j] == -1 && officerPos != i) {
d[j]++;
pos[j] = cur;
expand(j);
}
}
}
}
}
int loc;
int start(int N, bool A[MAX_N][MAX_N]) {
memset(siz, 0, sizeof siz);
for (int i = 0; i < M; i++)
pos[i] = -2;
memset(good, -1, sizeof good);
memset(d, 0, sizeof d);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (A[i][j])
g[i].push_back(j);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (i != j) {
siz[enc(i, j, 0)]++;
siz[enc(i, j, 0)] += g[i].size();
siz[enc(i, j, 1)] += g[j].size();
}
for (int i = 0; i < N; i++) {
expand(enc(i, i, 0));
expand(enc(i, i, 1));
}
for (int i = 0; i < N; i++) {
bool no = 0;
for (int j = 0; j < N; j++)
no |= good[enc(i, j, 0)] == -1;
if (!no) {
loc = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
//cout << loc << " " << R << endl;
loc = good[enc(loc, R, 0)] % (maxN * maxN) / maxN;
return loc;
}
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from coprobber.cpp:2:
coprobber.cpp: In function 'void expand(int)':
coprobber.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(d[cur] <= siz[cur]);
~~~~~~~^~~~~~~~~~~
coprobber.cpp:22:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (d[cur] == siz[cur] || (cur / (maxN * maxN) == 0 && d[cur]))
~~~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
7 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
66 ms |
9692 KB |
Output is correct |
5 |
Correct |
21 ms |
8832 KB |
Output is correct |
6 |
Correct |
79 ms |
9464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8192 KB |
Output is correct |
3 |
Correct |
74 ms |
9592 KB |
Output is correct |
4 |
Correct |
67 ms |
9592 KB |
Output is correct |
5 |
Correct |
70 ms |
9592 KB |
Output is correct |
6 |
Correct |
67 ms |
9592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
7 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
8 ms |
8192 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
7 ms |
8192 KB |
Output is correct |
7 |
Correct |
8 ms |
8192 KB |
Output is correct |
8 |
Correct |
8 ms |
8192 KB |
Output is correct |
9 |
Correct |
8 ms |
8192 KB |
Output is correct |
10 |
Correct |
9 ms |
8192 KB |
Output is correct |
11 |
Correct |
10 ms |
8320 KB |
Output is correct |
12 |
Correct |
9 ms |
8192 KB |
Output is correct |
13 |
Correct |
8 ms |
8192 KB |
Output is correct |
14 |
Correct |
10 ms |
8192 KB |
Output is correct |
15 |
Correct |
9 ms |
8320 KB |
Output is correct |
16 |
Correct |
9 ms |
8320 KB |
Output is correct |
17 |
Correct |
12 ms |
8448 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
7 ms |
8164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
65 ms |
9776 KB |
Output is correct |
5 |
Correct |
21 ms |
8832 KB |
Output is correct |
6 |
Correct |
72 ms |
9464 KB |
Output is correct |
7 |
Correct |
7 ms |
8220 KB |
Output is correct |
8 |
Correct |
8 ms |
8192 KB |
Output is correct |
9 |
Correct |
70 ms |
9592 KB |
Output is correct |
10 |
Correct |
67 ms |
9640 KB |
Output is correct |
11 |
Correct |
69 ms |
9592 KB |
Output is correct |
12 |
Correct |
71 ms |
9592 KB |
Output is correct |
13 |
Correct |
7 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
7 ms |
8192 KB |
Output is correct |
16 |
Correct |
8 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
9 ms |
8192 KB |
Output is correct |
19 |
Correct |
9 ms |
8192 KB |
Output is correct |
20 |
Correct |
8 ms |
8192 KB |
Output is correct |
21 |
Correct |
9 ms |
8192 KB |
Output is correct |
22 |
Correct |
9 ms |
8448 KB |
Output is correct |
23 |
Correct |
8 ms |
8320 KB |
Output is correct |
24 |
Correct |
12 ms |
8448 KB |
Output is correct |
25 |
Correct |
9 ms |
8192 KB |
Output is correct |
26 |
Correct |
11 ms |
8320 KB |
Output is correct |
27 |
Correct |
20 ms |
8440 KB |
Output is correct |
28 |
Correct |
29 ms |
8440 KB |
Output is correct |
29 |
Correct |
544 ms |
10472 KB |
Output is correct |
30 |
Correct |
77 ms |
8952 KB |
Output is correct |
31 |
Correct |
72 ms |
8824 KB |
Output is correct |
32 |
Correct |
417 ms |
10560 KB |
Output is correct |
33 |
Correct |
78 ms |
8568 KB |
Output is correct |
34 |
Correct |
545 ms |
10616 KB |
Output is correct |
35 |
Correct |
116 ms |
9464 KB |
Output is correct |
36 |
Correct |
384 ms |
9936 KB |
Output is correct |
37 |
Correct |
146 ms |
8696 KB |
Output is correct |
38 |
Correct |
8 ms |
8192 KB |
Output is correct |