#include "coprobber.h"
#include<iostream>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAX_N 500
#define ll long long
using namespace std;
struct state{
int who; // 0 - cop plays next, 1 rob plays next
int cop;
int rob;
};
int leftToWin[MAX_N][MAX_N][2],nextPos[MAX_N][MAX_N],curpos=0;
int start(int N, bool A[MAX_N][MAX_N])
{
rep(i,0,N)
{
int deg = 0;
rep(j,0,N)
{
if(A[i][j])
deg++;
}
rep(j,0,N)
{
if(i != j)
{
leftToWin[j][i][0] = 1;
leftToWin[j][i][1] = deg;
}
}
}
queue < state > q;
rep(i,0,N)
{
state s;
s.cop = i;
s.rob = i;
s.who = 0;
q.push(s);
s.who = 1;
q.push(s);
}
int totalstates = 0;
while(!q.empty())
{
state cur = q.front();
q.pop();
totalstates++;
// cout << cur.cop << " " << cur.rob << " " << cur.who << endl;
if(cur.who == 0)
{
rep(i,0,N)
{
if(A[i][cur.rob] && leftToWin[cur.cop][i][1] != 0)
{
leftToWin[cur.cop][i][1]--;
if(leftToWin[cur.cop][i][1] == 0)
{
state neo = cur;
neo.rob = i;
neo.who = 1;
q.push(neo);
}
}
}
}
else
{
rep(i,0,N)
{
if((A[cur.cop][i] || cur.cop == i) && leftToWin[i][cur.rob][0] != 0)
{
leftToWin[i][cur.rob][0] = 0;
state neo = cur;
neo.cop = i;
neo.who = 0;
q.push(neo);
nextPos[i][cur.rob] = cur.cop;
}
}
}
}
return totalstates == 2*N*N ? 0 : -1;
}
int nextMove(int R)
{
return curpos = nextPos[curpos][R];
}
/*
int main()
{
int n;
cin >> n;
bool a[MAX_N][MAX_N];
rep(i,0,n)
{
rep(j,0,n)
{
cin >> a[i][j];
}
}
cout<<start(n,a) << endl;
while(true)
{
int x;
cin >> x;
cout << nextMove(x) << endl;
}
}
*/
# |
결과 |
실행 시간 |
메모리 |
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 |
251 ms |
4720 KB |
Output is correct |
5 |
Correct |
37 ms |
2432 KB |
Output is correct |
6 |
Correct |
319 ms |
4964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
254 ms |
4728 KB |
Output is correct |
4 |
Correct |
250 ms |
4684 KB |
Output is correct |
5 |
Correct |
233 ms |
4748 KB |
Output is correct |
6 |
Correct |
285 ms |
4600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
304 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 |
384 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 |
4 ms |
1024 KB |
Output is correct |
11 |
Correct |
4 ms |
1024 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
3 ms |
896 KB |
Output is correct |
14 |
Correct |
5 ms |
1024 KB |
Output is correct |
15 |
Correct |
3 ms |
768 KB |
Output is correct |
16 |
Correct |
4 ms |
768 KB |
Output is correct |
17 |
Correct |
8 ms |
1280 KB |
Output is correct |
18 |
Correct |
3 ms |
1024 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
238 ms |
4812 KB |
Output is correct |
5 |
Correct |
37 ms |
2432 KB |
Output is correct |
6 |
Correct |
303 ms |
5112 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
247 ms |
4688 KB |
Output is correct |
10 |
Correct |
245 ms |
4708 KB |
Output is correct |
11 |
Correct |
232 ms |
4640 KB |
Output is correct |
12 |
Correct |
280 ms |
4600 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 |
512 KB |
Output is correct |
17 |
Correct |
4 ms |
1024 KB |
Output is correct |
18 |
Correct |
5 ms |
1024 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
3 ms |
896 KB |
Output is correct |
21 |
Correct |
4 ms |
1024 KB |
Output is correct |
22 |
Correct |
4 ms |
740 KB |
Output is correct |
23 |
Correct |
3 ms |
768 KB |
Output is correct |
24 |
Correct |
8 ms |
1280 KB |
Output is correct |
25 |
Correct |
3 ms |
1024 KB |
Output is correct |
26 |
Correct |
7 ms |
1664 KB |
Output is correct |
27 |
Correct |
17 ms |
2944 KB |
Output is correct |
28 |
Correct |
28 ms |
3584 KB |
Output is correct |
29 |
Correct |
384 ms |
7772 KB |
Output is correct |
30 |
Correct |
73 ms |
4312 KB |
Output is correct |
31 |
Correct |
78 ms |
4316 KB |
Output is correct |
32 |
Correct |
374 ms |
6392 KB |
Output is correct |
33 |
Correct |
98 ms |
4088 KB |
Output is correct |
34 |
Correct |
450 ms |
7324 KB |
Output is correct |
35 |
Correct |
282 ms |
5240 KB |
Output is correct |
36 |
Correct |
446 ms |
6288 KB |
Output is correct |
37 |
Correct |
217 ms |
4044 KB |
Output is correct |
38 |
Correct |
2 ms |
384 KB |
Output is correct |