Submission #959154

#	Time	Username	Problem	Language	Result	Execution time	Memory
959154		berr	Cop and Robber (BOI14_coprobber)	C++17	Compilation error	0 ms	0 KiB

coprobber

#include <cstdio>
#include <utility>
#include <bits/stdc++.h>

#include "coprobber.h"

using namespace std;

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;
int pos;
map<array<int, 2>, int> mp;
int state[500][500][2];
vector<vector<int>> g(500);

int calc(int x, int y, int player){
    if(x==y&&player==0) return state[x][y][player]=x;
    else if(x==y)return state[x][y][player]=-1;
    if(state[x][y][player]!=-2)return state[x][y][player];
  

    if(player==0){
        int c=0;
        state[x][y][player]=-1; //-1 means holding 

        for(auto i: g[x]){
            if(calc(i, y, 1)==-1){
                state[x][y][0]=i;
                c++;
            }
        }

        if(calc(x, y, 1)==-1){
            state[x][y][0]=x;
            c++;
        }

        if(!c) state[x][y][player]=-1;

    }
    else{
        int c=0;    
        state[x][y][player]=0;

        for(auto i: g[y]){
            if(calc(x, i, 0)==-1){
                state[x][y][1]=i;
                c++;
            }
        }

        if(!c){
            state[x][y][player]=-1;

         /*   for(auto i: g[x])
                state[i][y][0]=x;*/
        }

    }

    return state[x][y][player];
};

int start(int n, bool a[MAX_N][MAX_N]) {


    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            state[i][l][0]=-2; 
            state[i][l][1]=-2;
            if(a[i][l]){
                g[i].push_back(l);
            }
        }
    }

    for(int i=0; i<n; i++){
        int flag=1;
        for(int l=0; l<n; l++){
            if(calc(i, l, 1)!=-1){
                flag=0;
            }
        }
        if(flag) return pos=i;
    }

    return -1;
}

int nextMove(int R) {
    return pos = calc(pos, R, 0);
} 








  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 'int main()':
coprobber.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
coprobber.cpp:172:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |             scanf("%d", &t);
      |             ~~~~~^~~~~~~~~~
coprobber.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |     scanf("%d", &CopCanWin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
coprobber.cpp:180:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |                 scanf("%d", &RobberStrategy[c][r]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccLJt4sW.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYckICT.o:coprobber.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status