#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*2];
vector<int> adjr[maxn*maxn*2], adj[maxn*maxn*2];
bool win[maxn*maxn*2], B[maxn][maxn];
int nxt[maxn*maxn*2];
void calc(){
// rep(i,0,n) rep(j,0,n){
// cout << i << ' ' << j << ": \n";
// for(int c: adj[state(i, j, 0).id]){
// cout << state(c).u << ' ' << state(c).v << '\n';
// }
// }
vector<int> winners;
rep(i,0,n) rep(t,0,2) winners.pb(state(i, i, t).id);
while(sz(winners)){
int r = winners.back(); winners.pop_back();
win[r] = true;
state R(r);
for(int c: adjr[r]){
if(win[c]) continue;
cnt[c]++;
state S(c);
if(S.nb){
if(cnt[c] == sz(adj[c])) winners.pb(c);
}else winners.pb(c), nxt[c] = R.u;
}
}
}
void add_edge(state a, state b){
adj[a.id].pb(b.id);
adjr[b.id].pb(a.id);
}
state cr;
int nextMove(int r){
cr = state(cr.u, r, 0);
assert(B[cr.u][nxt[cr.id]] || cr.u == n);
cr = state(nxt[cr.id], r, 1);
assert(cr.u < n);
return cr.u;
}
int start(int n, bool A[MAX_N][MAX_N]){ ::n = n;
rep(i,0,n) rep(j,0,n) {
if(A[i][j]){
B[i][j] = true;
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) {
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();
if(!win[state(n, n, 0).id]) return -1;
cr = state(n, n, 0);
return nxt[cr.id];
}
// 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) {
// 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();
// if(!win[state(n, n, 0).id]) return cout << -1 << '\n', 0;
// cr = state(n, n, 0);
// cout << '#' <<nxt[cr.id] << endl;
// while(cr.u - cr.v || cr.u == n){
// int a; cin >> a;
// cout << '#' << nextMove(a) << endl;
// }
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23888 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23964 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23900 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
48336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23940 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23888 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
24024 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23888 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23964 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
23900 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 4 |
Halted |
0 ms |
0 KB |
- |
