| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 959154 | berr | 경찰관과 강도 (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}