Submission #569151

#	Time	Username	Problem	Language	Result	Execution time	Memory
569151		perchuts	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	336 KiB

coprobber

#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][1]==-1)dfs(v,y,1);
            if(dp[v][y][1]==0)can = 0, res = v;
        }
        if(dp[x][y][1]==-1)dfs(x,y,1);
        if(dp[x][y][1]==0)can = 0, res = x;
        dp[x][y][0] = can, where[atual][x][y] = res;
    }else{
        bool can = 0;
        for(auto v:g[y]){
            if(dp[x][v][0]==-1)dfs(x,v,0);
            if(dp[x][y][0]!=0)can=1;
        }
        dp[x][y][1] = can;
    }
    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 (stderr)

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;
      |                    ~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40