제출 #135840

#제출 시각아이디문제언어결과실행 시간메모리
135840tdwn경찰관과 강도 (BOI14_coprobber)C++17
0 / 100
2 ms504 KiB
#include "coprobber.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 510; class game_state { public: int c, r, turn; }; bool winning[maxn][maxn][2]; bool visited[maxn][maxn][2]; int g_cnt[maxn][maxn][2]; int g[maxn]; int nxt_move[maxn][maxn][2]; int position; int start(int N, bool A[MAX_N][MAX_N]) { queue<game_state>q; for(int i=0;i<N;i++) { winning[i][i][0] = winning[i][i][1] = true; visited[i][i][0] = winning[i][i][1] = true; q.push({i, i, 0}); q.push({i, i, 1}); } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(A[i][j]) g[i]++; } } for(int c=0;c<N;c++) { for(int r=0;r<N;r++) { g_cnt[c][r][1] = g[r]; } } // Doing everything backwards while(!q.empty()) { int cop = q.front().c; int robber = q.front().r; int turn = q.front().turn; q.pop(); // From which states is this state reachable /*cout<<"Winning state is: "<<cop<<" "<<robber<<" with turn on "; if(turn == 0) cout<<"police\n"; else cout<<"robber\n";*/ if(turn == 1) { for(int i=0;i<N;i++) { if(i == cop || A[i][cop]) { if(!visited[i][robber][0]) { winning[i][robber][0] = visited[i][robber][0] = true; nxt_move[i][robber][0] = cop; q.push({i, robber, 0}); } } } } else { // robber's turn, this is winning state, in order to make other state winning state // we should make sure each move to that state is winning move for(int i=0;i<N;i++) { if(A[robber][i]) { g_cnt[cop][i][1]--; if(g_cnt[cop][i][1] == 0 && !visited[cop][i][1]) { visited[cop][i][1] = winning[cop][i][1] = true; nxt_move[cop][i][1] = robber; q.push({cop, i, 1}); } } } } } for(int cop=0;cop<N;cop++) { int br = 0; for(int r=0;r<N;r++) { if(winning[cop][r][0]) br++; } if(br == N) { position = cop; return cop; } } return -1; } int nextMove(int R) { return nxt_move[position][R][0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...