#include <stdio.h>
#include <queue>
#include "coprobber.h"
using namespace std;
int dp[2][500][500]; //dp[police=0, thief=1][police][thief]
int cnt[2][500][500];
int adj[500];
int vs[2][500][500];
queue<pair<int, pair<int, int>>> q;
int pos;
int start(int N, bool A[MAX_N][MAX_N]){
for(int i=0; i<N; i++) for(int j=0; j<N; j++) dp[0][i][j] = -1, dp[1][i][j] = -1;
for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(A[i][j]) adj[i]++;
for(int i=0; i<N; i++){
dp[1][i][i] = -1;
q.push({1, {i, i}});
/*
for(int j=0; j<N; j++) if(A[i][j]){
cnt[1][i][j]++;
if(cnt[1][i][j] == adj[j]){
q.push({1, {i, j}});
}
}
dp[1][i][i] = -1;
for(int j=0; j<N; j++) if(A[i][j] || i == j){
dp[0][j][i] = i;
q.push({0, {j, i}});
}
*/
}
while(!q.empty()){
int st = q.front().first;
int pol = q.front().second.first, thief = q.front().second.second;
q.pop();
if(vs[st][pol][thief]) continue;
vs[st][pol][thief] = 1;
if(st){
// thief's turn --> updating police's turns
if(dp[st][pol][thief] == -1){
// thief loses --> neighboring polices win
for(int i=0; i<N; i++){
if(!A[i][pol] && i != pol) continue;
if(dp[0][i][thief] == -1){
dp[0][i][thief] = pol;
q.push({0, {i, thief}});
}
}
} else{
// thief wins --> neighboring polices might lose
for(int i=0; i<N; i++){
if(!A[i][pol] && i != pol) continue;
cnt[0][i][thief]++;
if(cnt[0][i][thief] == adj[i]+1){
q.push({0, {i, thief}});
}
}
}
} else{
// police's turn --> updating thief's turns
if(dp[st][pol][thief] == -1){
// police loses --> neighboring thieves win
for(int i=0; i<N; i++){
if(!A[i][thief]) continue;
if(dp[1][pol][i] == -1){
dp[1][pol][i] = thief;
q.push({1, {pol, i}});
}
}
} else{
// police wins --> neighboring thieves might lose
for(int i=0; i<N; i++){
if(!A[i][thief]) continue;
cnt[1][pol][i]++;
if(cnt[1][pol][i] == adj[i]){
q.push({1, {pol, i}});
}
}
}
}
}
for(int i=0; i<N; i++){
int ok = 0;
for(int j=0; j<N; j++){
if(dp[0][i][j] != -1) ok++;
}
if(ok == N){
pos = i;
return i;
}
}
return -1;
}
int nextMove(int R){
pos = dp[0][pos][R];
return pos;
}
# |
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 |
267 ms |
6636 KB |
Output is correct |
5 |
Correct |
41 ms |
3448 KB |
Output is correct |
6 |
Correct |
350 ms |
6972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
288 ms |
6648 KB |
Output is correct |
4 |
Correct |
264 ms |
6776 KB |
Output is correct |
5 |
Correct |
274 ms |
6528 KB |
Output is correct |
6 |
Correct |
324 ms |
6652 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 |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
484 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
428 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
4 ms |
1408 KB |
Output is correct |
11 |
Correct |
5 ms |
1408 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
3 ms |
1152 KB |
Output is correct |
14 |
Correct |
5 ms |
1408 KB |
Output is correct |
15 |
Correct |
3 ms |
896 KB |
Output is correct |
16 |
Correct |
3 ms |
896 KB |
Output is correct |
17 |
Correct |
9 ms |
1664 KB |
Output is correct |
18 |
Correct |
3 ms |
1408 KB |
Output is correct |
19 |
Correct |
2 ms |
384 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 |
512 KB |
Output is correct |
4 |
Correct |
264 ms |
6648 KB |
Output is correct |
5 |
Correct |
40 ms |
3448 KB |
Output is correct |
6 |
Correct |
384 ms |
7008 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
278 ms |
6732 KB |
Output is correct |
10 |
Correct |
263 ms |
6776 KB |
Output is correct |
11 |
Correct |
272 ms |
6648 KB |
Output is correct |
12 |
Correct |
310 ms |
6520 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
640 KB |
Output is correct |
17 |
Correct |
4 ms |
1408 KB |
Output is correct |
18 |
Correct |
4 ms |
1408 KB |
Output is correct |
19 |
Correct |
2 ms |
640 KB |
Output is correct |
20 |
Correct |
4 ms |
1152 KB |
Output is correct |
21 |
Correct |
5 ms |
1408 KB |
Output is correct |
22 |
Correct |
3 ms |
896 KB |
Output is correct |
23 |
Correct |
4 ms |
1024 KB |
Output is correct |
24 |
Correct |
10 ms |
1664 KB |
Output is correct |
25 |
Correct |
4 ms |
1408 KB |
Output is correct |
26 |
Correct |
7 ms |
2432 KB |
Output is correct |
27 |
Correct |
19 ms |
4480 KB |
Output is correct |
28 |
Correct |
31 ms |
5596 KB |
Output is correct |
29 |
Correct |
451 ms |
9676 KB |
Output is correct |
30 |
Correct |
65 ms |
6024 KB |
Output is correct |
31 |
Correct |
68 ms |
6520 KB |
Output is correct |
32 |
Correct |
493 ms |
8568 KB |
Output is correct |
33 |
Correct |
83 ms |
6136 KB |
Output is correct |
34 |
Correct |
582 ms |
9476 KB |
Output is correct |
35 |
Correct |
316 ms |
7112 KB |
Output is correct |
36 |
Correct |
552 ms |
8508 KB |
Output is correct |
37 |
Correct |
235 ms |
5888 KB |
Output is correct |
38 |
Correct |
2 ms |
384 KB |
Output is correct |