Submission #568489

#TimeUsernameProblemLanguageResultExecution timeMemory
568489hollwo_pelwKoala Game (APIO17_koala)C++17
90 / 100
46 ms720 KiB
#include <bits/stdc++.h> using namespace std; #include "koala.h" int R[105], B[105]; void __init__() { memset(R, 0, sizeof R); memset(B, 0, sizeof B); } int minValue(int N, int W) { __init__(); B[0] = 1; playRound(B, R); for (int i = 1; i < N; i++) if (!R[i]) return i; return 0; } int maxValue(int N, int W) { vector<int> res(N); iota(res.begin(), res.end(), 0); while ((int) res.size() > 1) { __init__(); for (auto i : res) B[i] = W / res.size(); playRound(B, R); int f = *max_element(R, R + N); res.clear(); for (int i = 0; i < N; i++) if (R[i] == f) res.push_back(i); } return res[0]; } int greaterValue(int N, int W) { int l = 0, r = sqrt(N * 2); while (l <= r) { int mid = (l + r) >> 1; __init__(); B[0] = B[1] = mid; playRound(B, R); int c0 = R[0] > B[0], c1 = R[1] > B[1]; if (c0 ^ c1) { if (c0) return 0; if (c1) return 1; } if (c0) { l = mid + 1; } else { r = mid - 1; } } return 0; } int dp[105][205], ct[105][205], need[105]; inline int get_p(int N, int W, int LL, int RR) { for (int p = 1; p <= W; p++) { memset(dp, 0, sizeof dp); memset(ct, 0, sizeof ct); fill(need + 1, need + N + 1, 1); for (int i = LL; i <= RR; i++) need[i] = p + 1; for (int i = 1; i <= N; i++) { for (int j = 0; j <= W; j++) { dp[i][j] = dp[i - 1][j]; ct[i][j] = ct[i - 1][j]; if (j >= need[i] && dp[i][j] < dp[i - 1][j - need[i]] + i) { dp[i][j] = dp[i - 1][j - need[i]] + i; ct[i][j] = ct[i - 1][j - need[i]] + (i <= RR && i >= LL); } } } if (ct[N][W] > 0 && ct[N][W] < RR - LL + 1) return p; } return 0; } void solve(int LL, int RR, int W, int *P, vector<int> pos) { if (LL == RR) { assert((int) pos.size() == 1); return P[pos[0]] = LL, (void) 0; } vector<int> lef, rig; int f = get_p(W, W, LL, RR); __init__(); for (int i : pos) B[i] = f; playRound(B, R); for (int i : pos) { if (R[i] > B[i]) rig.push_back(i); else lef.push_back(i); } int mid = LL + lef.size(); solve(LL, mid - 1, W, P, lef), solve(mid, RR, W, P, rig); } void allValues(int N, int W, int *P) { vector<int> pos(N); iota(pos.begin(), pos.end(), 0); if (W == 2*N) { solve(1, N, W, P, pos); } else { solve(1, N, W, P, pos); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...