#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss secounf
#define all(x) begin(x), end(x)
#define pb push_back
const ll mod = 1e9+7, maxn = 5e2+1, inf = ll(1e9)+5;
struct state{
int u, v, id;
bool nb;
state(){}
state(int u, int v, int nb): u(u), v(v), nb(nb){
id = (u*maxn + v)<<1|nb;
}
state(int id): id(id){
nb = id&1, id >>= 1;
v = id%maxn, u = id/maxn;
}
};
int n, cnt[maxn*maxn];
state SS[maxn*maxn*2];
int SID[maxn][maxn][2], SIDd[maxn][maxn];
// vector<int> adjr[maxn*maxn*2];
// bool win[maxn*maxn*2];
bitset<maxn*maxn*2> win;
bool B[maxn][maxn];
int nxt[maxn*maxn], out[maxn*maxn];
#define MAX_N 500
vector<int> adjr(state a){
vector<int> res; res.reserve(n+1);
if(a.nb){
rep(i,0,n) if(B[i][a.u]) res.pb(SID[i][a.v][0]);
res.pb(a.id^1);
if(a.v == n) res.pb(SID[n][n][0]);
}else{
rep(i,0,n) if(B[i][a.v]) res.pb(SID[a.u][i][1]);
res.pb(SID[a.u][n][1]);
}
return res;
}
void calc(){
vector<int> winners;
rep(i,0,n) rep(t,0,2) winners.pb(SID[i][i][t]), win[winners.back()] = true;
int id = 0;
while(sz(winners)){
int r = winners.back(); winners.pop_back();
state R = SS[r];
// cout << r << endl;
for(int c: adjr(R)){
if(win[c]) continue;
id = c, c>>=1;
if(id&1){
cnt[c]++;
if(cnt[c] == out[c]) {
winners.pb(id);
win[winners.back()] = true;
}
}else winners.pb(id), nxt[c] = R.u, win[winners.back()] = true;
}
}
}
int u, v;
int nextMove(int r){
v = r, u = nxt[SIDd[u][v]];
return u;
}
int start(int n, bool A[MAX_N][MAX_N]){ ::n = n;
rep(i,0,n+1) rep(j,0,n+1) rep(t,0,2) SID[i][j][t] = state(i, j, t).id, SIDd[i][j] = SID[i][j][0]>>1;
rep(i,0,maxn*maxn*2) SS[i] = state(i);
rep(i,0,n) rep(j,0,n) {
if(A[i][j]){
B[i][j] = true;
rep(a,0,n) {
out[SIDd[a][i]]++;
}
}
}
rep(i,0,n) {
rep(j,0,n) out[SIDd[i][n]]++;
}
calc();
if(!win[SID[n][n][0]]) return -1;
u = nxt[SIDd[n][n]], v = n;
return u;
}
// don't modify the main function
// int main() {
// cin.tie(0) -> sync_with_stdio(0);
// int N;
// cin >> N;
// bool A[MAX_N][MAX_N];
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// cin >> A[i][j];
// }
// }
// int P = start(N,A);
// cout << P << endl;
// int R;
// cin >> R;
// while (true) {
// if (P == R) break;
// P = nextMove(R);
// cout << P << endl;
// if (P == R) break;
// cin >> R;
// }
// }
// int main(){
// cin.tie(0) -> sync_with_stdio(0);
// cin >> n;
// rep(i,0,n) rep(j,0,n) {
// bool k; cin >> k;
// if(k){
// rep(a,0,n) {
// add_edge(state(a, i, 1), state(a, j, 0));
// add_edge(state(i, a, 0), state(j, a, 1));
// }
// }
// }
// rep(i,0,n) rep(j,0,n) add_edge(state(i, j, 0), state(i, j, 1));
// rep(i,0,n) {
// add_edge(state(n, n, 0), state(i, n, 1));
// rep(j,0,n) add_edge(state(i, n, 1), state(i, j, 0));
// }
// calc();
// rep(i,0,n) rep(j,0,n) {
// int ID = state(i, j, 0).id;
// if(!win[ID]) cout << -1 << ' ';
// else cout << i << ',' << j << ',' << nxt[ID] << ' ';
// if(j == n-1) cout << '\n';
// }
// if(!win[state(n, n, 0).id]) return -1;
// cr = state(nxt[state(n, n, 0).id], n, 1);
// cout << '#' << cr.u << endl;
// while(cr.u - cr.v || cr.u == n){
// int a; cin >> a;
// cout << '#' << nextMove(a) << endl;
// }
// return 0;
// }
/*
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
3
0 1 1
1 0 1
1 1 0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8144 KB |
Output is correct |
2 |
Correct |
4 ms |
8272 KB |
Output is correct |
3 |
Correct |
4 ms |
8272 KB |
Output is correct |
4 |
Correct |
322 ms |
15796 KB |
Output is correct |
5 |
Correct |
46 ms |
11700 KB |
Output is correct |
6 |
Correct |
366 ms |
15592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8272 KB |
Output is correct |
2 |
Correct |
5 ms |
8272 KB |
Output is correct |
3 |
Correct |
313 ms |
15560 KB |
Output is correct |
4 |
Correct |
323 ms |
15696 KB |
Output is correct |
5 |
Correct |
306 ms |
15444 KB |
Output is correct |
6 |
Correct |
356 ms |
15560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8144 KB |
Output is correct |
2 |
Correct |
4 ms |
8144 KB |
Output is correct |
3 |
Correct |
4 ms |
8272 KB |
Output is correct |
4 |
Correct |
4 ms |
8272 KB |
Output is correct |
5 |
Correct |
4 ms |
8272 KB |
Output is correct |
6 |
Correct |
4 ms |
8144 KB |
Output is correct |
7 |
Correct |
5 ms |
8272 KB |
Output is correct |
8 |
Correct |
5 ms |
8272 KB |
Output is correct |
9 |
Correct |
5 ms |
8400 KB |
Output is correct |
10 |
Correct |
7 ms |
9424 KB |
Output is correct |
11 |
Correct |
10 ms |
9416 KB |
Output is correct |
12 |
Correct |
4 ms |
8528 KB |
Output is correct |
13 |
Correct |
5 ms |
9156 KB |
Output is correct |
14 |
Correct |
8 ms |
9424 KB |
Output is correct |
15 |
Correct |
5 ms |
8912 KB |
Output is correct |
16 |
Correct |
8 ms |
8900 KB |
Output is correct |
17 |
Correct |
18 ms |
9692 KB |
Output is correct |
18 |
Correct |
6 ms |
9468 KB |
Output is correct |
19 |
Correct |
4 ms |
8144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8144 KB |
Output is correct |
2 |
Correct |
4 ms |
8272 KB |
Output is correct |
3 |
Correct |
4 ms |
8272 KB |
Output is correct |
4 |
Correct |
322 ms |
15796 KB |
Output is correct |
5 |
Correct |
46 ms |
11700 KB |
Output is correct |
6 |
Correct |
366 ms |
15592 KB |
Output is correct |
7 |
Correct |
4 ms |
8272 KB |
Output is correct |
8 |
Correct |
5 ms |
8272 KB |
Output is correct |
9 |
Correct |
313 ms |
15560 KB |
Output is correct |
10 |
Correct |
323 ms |
15696 KB |
Output is correct |
11 |
Correct |
306 ms |
15444 KB |
Output is correct |
12 |
Correct |
356 ms |
15560 KB |
Output is correct |
13 |
Correct |
4 ms |
8144 KB |
Output is correct |
14 |
Correct |
4 ms |
8144 KB |
Output is correct |
15 |
Correct |
4 ms |
8272 KB |
Output is correct |
16 |
Correct |
4 ms |
8272 KB |
Output is correct |
17 |
Correct |
4 ms |
8272 KB |
Output is correct |
18 |
Correct |
4 ms |
8144 KB |
Output is correct |
19 |
Correct |
5 ms |
8272 KB |
Output is correct |
20 |
Correct |
5 ms |
8272 KB |
Output is correct |
21 |
Correct |
5 ms |
8400 KB |
Output is correct |
22 |
Correct |
7 ms |
9424 KB |
Output is correct |
23 |
Correct |
10 ms |
9416 KB |
Output is correct |
24 |
Correct |
4 ms |
8528 KB |
Output is correct |
25 |
Correct |
5 ms |
9156 KB |
Output is correct |
26 |
Correct |
8 ms |
9424 KB |
Output is correct |
27 |
Correct |
5 ms |
8912 KB |
Output is correct |
28 |
Correct |
8 ms |
8900 KB |
Output is correct |
29 |
Correct |
18 ms |
9692 KB |
Output is correct |
30 |
Correct |
6 ms |
9468 KB |
Output is correct |
31 |
Correct |
4 ms |
8144 KB |
Output is correct |
32 |
Correct |
4 ms |
8144 KB |
Output is correct |
33 |
Correct |
4 ms |
8144 KB |
Output is correct |
34 |
Correct |
4 ms |
8272 KB |
Output is correct |
35 |
Correct |
350 ms |
15700 KB |
Output is correct |
36 |
Correct |
49 ms |
11720 KB |
Output is correct |
37 |
Correct |
333 ms |
15512 KB |
Output is correct |
38 |
Correct |
4 ms |
8272 KB |
Output is correct |
39 |
Correct |
4 ms |
8340 KB |
Output is correct |
40 |
Correct |
334 ms |
15608 KB |
Output is correct |
41 |
Correct |
333 ms |
15696 KB |
Output is correct |
42 |
Correct |
333 ms |
15488 KB |
Output is correct |
43 |
Correct |
327 ms |
15568 KB |
Output is correct |
44 |
Correct |
4 ms |
8144 KB |
Output is correct |
45 |
Correct |
6 ms |
8292 KB |
Output is correct |
46 |
Correct |
4 ms |
8272 KB |
Output is correct |
47 |
Correct |
4 ms |
8400 KB |
Output is correct |
48 |
Correct |
6 ms |
9424 KB |
Output is correct |
49 |
Correct |
10 ms |
9452 KB |
Output is correct |
50 |
Correct |
5 ms |
8528 KB |
Output is correct |
51 |
Correct |
6 ms |
9040 KB |
Output is correct |
52 |
Correct |
10 ms |
9416 KB |
Output is correct |
53 |
Correct |
5 ms |
8912 KB |
Output is correct |
54 |
Correct |
6 ms |
8912 KB |
Output is correct |
55 |
Correct |
16 ms |
9688 KB |
Output is correct |
56 |
Correct |
5 ms |
9424 KB |
Output is correct |
57 |
Correct |
10 ms |
10704 KB |
Output is correct |
58 |
Correct |
30 ms |
13264 KB |
Output is correct |
59 |
Correct |
39 ms |
14564 KB |
Output is correct |
60 |
Correct |
1428 ms |
15580 KB |
Output is correct |
61 |
Correct |
266 ms |
13960 KB |
Output is correct |
62 |
Correct |
242 ms |
14620 KB |
Output is correct |
63 |
Correct |
1140 ms |
15840 KB |
Output is correct |
64 |
Correct |
166 ms |
14704 KB |
Output is correct |
65 |
Correct |
1243 ms |
15668 KB |
Output is correct |
66 |
Correct |
360 ms |
15176 KB |
Output is correct |
67 |
Correct |
763 ms |
15584 KB |
Output is correct |
68 |
Correct |
356 ms |
14508 KB |
Output is correct |
69 |
Correct |
5 ms |
8144 KB |
Output is correct |