#include<bits/stdc++.h>
using namespace std;
int n , iswin [502][502][3] , nxt [502][502][3] , cur;
bool a [500][500];
int start(int N, bool A [500][500])
{
n = N;
for ( int i = 0 ; i < n ; i ++ )
{
for ( int j = 0 ; j < n ; j ++ ) a [i][j] = A [i][j];
iswin [i][i][0] = 1;
iswin [i][i][1] = 1;
}
while ( true )
{
int did = 0;
for ( int i = 0 ; i < n ; i ++ )
{
for ( int j = 0 ; j < n ; j ++ )
{
for ( int z = 0 ; z < 2 ; z ++ )
{
if ( iswin [i][j][z] ) continue;
int num = 0 , all = 0;
for ( int k = 0 ; k < n ; k ++ )
{
int nx = i , ny = j , can = 0 , zz = z ^ 1;
if ( zz == 0 )
{
ny = k;
if ( a [j][k] ) can = 1;
}
else
{
nx = k;
if ( a [i][k] ) can = 1;
}
if ( zz == 1 && i == k ) can = 1;
if ( can == 0 ) continue;
all ++;
if ( iswin [nx][ny][zz] )
{
nxt [i][j][z] = k;
num ++;
}
}
if ( ( z == 1 && all == num ) || ( z == 0 && num ) )
{
iswin [i][j][z] = 1;
did = 1;
}
}
}
}
if ( did == 0 ) break;
}
for ( int i = 0 ; i < n ; i ++ )
{
int num = 0;
for ( int j = 0 ; j < n ; j ++ )
{
if ( iswin [i][j][0] ) num ++;
}
if ( num == n )
{
cur = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
if ( cur == -1 ) return -1;
cur = nxt [cur][R][0];
return cur;
}
/*
int main()
{
cin >> n;
for ( int i = 0 ; i < n ; i ++ )
{
for ( int j = 0 ; j < n ; j ++ ) cin >> a [i][j];
}
cout << start ( n , a ) << endl;
while ( true )
{
int x;
cin >> x;
cout << ' ' << nextMove ( x ) << endl;
}
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Execution timed out |
3067 ms |
6076 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
464 KB |
Output is correct |
3 |
Execution timed out |
3066 ms |
7316 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
464 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
464 KB |
Output is correct |
10 |
Correct |
16 ms |
1308 KB |
Output is correct |
11 |
Correct |
19 ms |
1444 KB |
Output is correct |
12 |
Correct |
1 ms |
608 KB |
Output is correct |
13 |
Correct |
11 ms |
1116 KB |
Output is correct |
14 |
Correct |
54 ms |
1424 KB |
Output is correct |
15 |
Correct |
5 ms |
848 KB |
Output is correct |
16 |
Correct |
9 ms |
844 KB |
Output is correct |
17 |
Correct |
83 ms |
1624 KB |
Output is correct |
18 |
Correct |
6 ms |
1232 KB |
Output is correct |
19 |
Correct |
0 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Execution timed out |
3067 ms |
6076 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |