#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[0][i][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 |
266 ms |
6648 KB |
Output is correct |
5 |
Correct |
41 ms |
3328 KB |
Output is correct |
6 |
Correct |
408 ms |
6884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
384 KB |
the situation repeated |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Incorrect |
2 ms |
384 KB |
the situation repeated |
5 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
303 ms |
6628 KB |
Output is correct |
5 |
Correct |
41 ms |
3328 KB |
Output is correct |
6 |
Correct |
390 ms |
6936 KB |
Output is correct |
7 |
Incorrect |
2 ms |
384 KB |
the situation repeated |
8 |
Halted |
0 ms |
0 KB |
- |