#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
bool G[505][505][2];
int R[505][505];
int AD[505];
int n;
tuple<int,int,int> P[505][505][2];
// Game Theory
// G[i][j][0] wins if there is a k such that G[k][j][1] is winning
// G[i][j][1] wins if all k adjacence to j G[i][k][0] is true
int currA = 0 , currB = -1;
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
queue<tuple<int,int,int > > q;
for(int i = 0 ; i < N ; i++){
G[i][i][0] = 1;
G[i][i][1] = 1;
q.push(make_tuple(i,i,0));
q.push(make_tuple(i,i,1));
}
// fill R[][]
for(int i = 0 ; i < n; i++){
for(int j = 0 ; j < n; j ++){
for(int k = 0 ; k < n; k ++){
if(k == j) continue;
R[i][j] = R[i][j] + A[j][k];
}
}
}
while(!q.empty()){
tuple<int,int,int> u = q.front();
q.pop();
if(get<2>(u)){
for(int i = 0 ; i < n; i++){
if(A[i][get<0>(u)] || i == get<0>(u)){
if(G[i][get<1>(u)][0] == 0){
G[i][get<1>(u)][0] = 1;
tuple<int,int,int> t = u;
get<0>(t) = i, get<2>(t) = 0;
P[get<0>(t)][get<1>(t)][get<2>(t)] = u;
q.push(t);
}
}
}
}
else{
for(int i = 0 ; i < n; i ++){
if(A[i][get<1>(u)]){
R[get<0>(u)][i]--;
if(R[get<0>(u)][i] == 0){
G[get<0>(u)][i][1] = true;
tuple<int,int,int> t = u;
get<1>(t) = i;
get<2>(t) = 1;
P[get<0>(t)][get<1>(t)][get<2>(t)] = u;
//cout<< get<0>(u) <<" " << get<1>(u) <<" " << get<2>(u) << endl;
//cout<< get<0>(t) <<" " << get<1>(t) <<" " << get<2>(t) << endl;
q.push(t);
}
}
}
}
}
bool can = true;
for(int i = 0 ; i < n; i ++){
if(!G[0][i][0]) can = false;
}
if(can){
return 0;
}
else{
return -1;
}
}
int nextMove(int R)
{
currB = R;
tuple<int,int,int> L = P[currA][currB][0];
return currA = get<0>(L);
}
| # |
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 |
707 ms |
9352 KB |
Output is correct |
| 5 |
Correct |
73 ms |
4088 KB |
Output is correct |
| 6 |
Correct |
628 ms |
9388 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 |
560 ms |
9200 KB |
Output is correct |
| 4 |
Correct |
570 ms |
9336 KB |
Output is correct |
| 5 |
Correct |
530 ms |
8984 KB |
Output is correct |
| 6 |
Correct |
604 ms |
9080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 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 |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
512 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1408 KB |
Output is correct |
| 12 |
Correct |
2 ms |
640 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
7 ms |
1452 KB |
Output is correct |
| 15 |
Correct |
3 ms |
896 KB |
Output is correct |
| 16 |
Correct |
4 ms |
896 KB |
Output is correct |
| 17 |
Correct |
10 ms |
1664 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1152 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 |
384 KB |
Output is correct |
| 4 |
Correct |
566 ms |
9404 KB |
Output is correct |
| 5 |
Correct |
73 ms |
4088 KB |
Output is correct |
| 6 |
Correct |
664 ms |
9488 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
581 ms |
9108 KB |
Output is correct |
| 10 |
Correct |
615 ms |
9228 KB |
Output is correct |
| 11 |
Correct |
552 ms |
9032 KB |
Output is correct |
| 12 |
Correct |
611 ms |
9208 KB |
Output is correct |
| 13 |
Correct |
3 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 |
512 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 18 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 19 |
Correct |
2 ms |
640 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 21 |
Correct |
7 ms |
1408 KB |
Output is correct |
| 22 |
Correct |
3 ms |
896 KB |
Output is correct |
| 23 |
Correct |
4 ms |
896 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1664 KB |
Output is correct |
| 25 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 26 |
Correct |
23 ms |
2560 KB |
Output is correct |
| 27 |
Correct |
154 ms |
5908 KB |
Output is correct |
| 28 |
Correct |
295 ms |
7988 KB |
Output is correct |
| 29 |
Correct |
702 ms |
12284 KB |
Output is correct |
| 30 |
Correct |
320 ms |
8312 KB |
Output is correct |
| 31 |
Correct |
461 ms |
8952 KB |
Output is correct |
| 32 |
Correct |
846 ms |
11032 KB |
Output is correct |
| 33 |
Correct |
372 ms |
8696 KB |
Output is correct |
| 34 |
Correct |
866 ms |
11932 KB |
Output is correct |
| 35 |
Correct |
610 ms |
9720 KB |
Output is correct |
| 36 |
Correct |
945 ms |
10896 KB |
Output is correct |
| 37 |
Correct |
532 ms |
8568 KB |
Output is correct |
| 38 |
Correct |
2 ms |
384 KB |
Output is correct |
