제출 #250555

#제출 시각아이디문제언어결과실행 시간메모리
250555opukittpceno_hhr경찰관과 강도 (BOI14_coprobber)C++17
60 / 100
1641 ms9864 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <chrono> #include <random> #include <functional> #define MAX_N 500 using namespace std; const int M = 500 * 500 * 2; int n, C; int loose[M]; int win[M]; int cnt[M]; int turn[M]; int used[M]; int grid[MAX_N][MAX_N]; void dfs(int v) { used[v] = 1; { int k = v; int t = k / (n * n); int st = k % (n * n); int i = st / n; int j = st % n; if (t == 0) { for (int to = 0; to < n; to++) { if (grid[to][j]) { int nw = n * n + i * n + to; if (used[nw]) continue; if (loose[v]) { win[nw] = 1; turn[nw] = v; dfs(nw); } else { cnt[nw]--; if (cnt[nw] == 0) { loose[nw] = 1; dfs(nw); } } } } } else { for (int to = 0; to < n; to++) { if (grid[to][i] || (i == to)) { int nw = to * n + j; if (used[nw]) continue; if (loose[v]) { win[nw] = 1; turn[nw] = v; dfs(nw); } else { cnt[nw]--; if (cnt[nw] == 0) { loose[nw] = 1; dfs(nw); } } } } } } } int start(int N, bool a[MAX_N][MAX_N]) { n = N; C = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { grid[i][j] = a[i][j]; } } for (int k = 0; k < 2 * n * n; k++) { int t = k / (n * n); int st = k % (n * n); int i = st / n; int j = st % n; if (t == 0) { for (int to = 0; to < n; to++) { if (a[i][to] || i == to) { cnt[k]++; } } } else { for (int to = 0; to < n; to++) { if (a[j][to]) { cnt[k]++; } } } } for (int i = 0; i < n; i++) { loose[n * n + i * n + i] = 1; } for (int i = 0; i < n; i++) { win[i * n + i] = 1; } for (int i = 0; i < 2 * n * n; i++) { if (!used[i] && (win[i] || loose[i])) { dfs(i); } } for (int i = 0; i < n; i++) { int ok = 1; for (int j = 0; j < n; j++) { ok &= win[i * n + j]; } if (ok) { C = i; return i; } } return -1; } int nextMove(int r) { if (!win[C * n + r]) { return -1; } int next_state = turn[C * n + r]; next_state %= (n * n); C = next_state / n; return C; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...