#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "coprobber.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 101;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<int>g[maxn];
int n, where[maxn][maxn][maxn], dp[maxn][maxn][2], atual;
bool dfs(int x,int y,bool player){
if(x==y)return dp[x][y][player] = 0;
dp[x][y][player] = 2;
if(player==0){
bool can = 1;
int res = -1;
for(auto v:g[x]){
if(dp[v][y][player^1]==-1)dfs(v,y,player^1);
if(dp[v][y][player^1]==0)can = 0, res = v;
}
if(dp[x][y][player^1]==-1)dfs(x,y,player^1);
if(dp[x][y][player^1]==0)can = 0, res = x;
dp[x][y][player] = can, where[atual][x][y] = res;
}else{
bool can = 0, ok = 1;
for(auto v:g[y]){
if(dp[x][v][player^1]==-1)dfs(x,v,player^1);
if(dp[x][y][player^1]!=0)can=1;
}
dp[x][y][player] = (can||ok);
}
return dp[x][y][player];
}
bool processa(int x,int y){
for(int i=0;i<n;++i)for(int j=0;j<n;++j)dp[i][j][0] = -1, dp[i][j][1] = -1;
atual = y;
return dfs(x,y,0)==0;
}
int ini = -1, current;
int start(int N, bool A[MAX_N][MAX_N])
{
//idea: minmax algo
//dp[i][j][x][y][2] => officer starts on i, robber on j, and current position of them
//is (x,y) and now its time for officer (0) or robber (1) to move
//need to optimize this to O(N^3)
n = N;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(A[i][j])g[i].pb(j);
for(int i=0;i<n;++i){
bool ok = 1;
for(int j=0;j<n;++j)ok &= processa(i,j);
if(ok)return i;
}
return -1;
}
int nextMove(int R)
{
if(ini==-1)ini = R;
return current = where[ini][current][R];
}
// static const bool TRACK_CALLS = false;
// static int N, CopCanWin;
// static bool A[MAX_N][MAX_N];
// // Where should the robber go if the first index is the cop's
// // position and the second index is the robber's position?
// // RS[c][N] stores robber's starting corners.
// static int RobberStrategy[MAX_N][MAX_N + 1];
// // Visited positions are stored in the following array
// static bool VisitedPositions[MAX_N][MAX_N];
// static const int OK = 0, PARTFAIL = 1, FAIL = 2;
// static const char* Messages[] = { "OK", "PARTFAIL", "FAIL" };
// typedef pair<int, const char*> GraderResult;
// static GraderResult runGrader() {
// int copCorner = start(N, A);
// if (TRACK_CALLS)
// fprintf(stderr, "start() = %d\n", copCorner);
// if ((copCorner != -1) && !CopCanWin)
// return GraderResult(FAIL, "Cop cannot catch the robber, but start() did not return -1");
// if ((copCorner == -1) && CopCanWin)
// return GraderResult(FAIL, "Cop can catch the robber, but start() returned -1");
// if (!CopCanWin)
// return GraderResult(OK, NULL);
// if (copCorner < 0 || copCorner >= N)
// return GraderResult(FAIL, "start() returned a value that is outside the 0..N-1 range");
// int robberCorner = RobberStrategy[copCorner][N];
// if (robberCorner == copCorner) // If N = 1
// return GraderResult(OK, NULL);
// while (true) {
// int nextCopCorner = nextMove(robberCorner);
// if (TRACK_CALLS)
// fprintf(stderr, "nextMove(%d) = %d\n", robberCorner, nextCopCorner);
// /**
// * Check if the move is valid:
// * - the returned corner is within bounds
// * - the new corner is either the same or is a neighbour to the old one
// */
// if (nextCopCorner < 0 || nextCopCorner >= N
// || !(copCorner == nextCopCorner || A[copCorner][nextCopCorner]))
// return GraderResult(PARTFAIL,
// "nextMove() returned a value that is either outside 0..N-1 "
// "or the new cop position is not a neighbour to the previous one");
// copCorner = nextCopCorner;
// // Check if the same position has not been encountered before
// if (VisitedPositions[copCorner][robberCorner])
// return GraderResult(PARTFAIL, "the situation repeated");
// VisitedPositions[copCorner][robberCorner] = true;
// // Check the winning condition
// if (copCorner == robberCorner)
// return GraderResult(OK, NULL);
// robberCorner = RobberStrategy[copCorner][robberCorner];
// // Moving to cop's position could have been the only
// // valid move for the robber
// if (copCorner == robberCorner)
// return GraderResult(OK, NULL);
// }
// }
// int main() {
// scanf("%d", &N);
// for (int i = 0; i < N; i++)
// for (int j = 0; j < N; j++) {
// int t;
// scanf("%d", &t);
// A[i][j] = t;
// }
// scanf("%d", &CopCanWin);
// if (CopCanWin) {
// for (int c = 0; c < N; c++)
// for (int r = 0; r <= N; r++)
// scanf("%d", &RobberStrategy[c][r]);
// }
// GraderResult result = runGrader();
// puts(Messages[result.first]);
// if (result.second != NULL)
// puts(result.second);
// return 0;
// }
Compilation message
coprobber.cpp: In function 'bool dfs(int, int, bool)':
coprobber.cpp:28:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
28 | if(x==y)return dp[x][y][player] = 0;
| ~~~~~~~~~~~~~~~~~^~~
| # |
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 |
Incorrect |
1 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
| 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 |
Incorrect |
1 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
