Submission #1199074

#TimeUsernameProblemLanguageResultExecution timeMemory
1199074thieunguyenhuyKoala Game (APIO17_koala)C++17
100 / 100
35 ms468 KiB
#ifndef hwe #include "koala.h" #endif #include <bits/stdc++.h> using namespace std; #define popcount(n) (__builtin_popcountll((n))) #define clz(n) (__builtin_clzll((n))) #define ctz(n) (__builtin_ctzll((n))) #define lg(n) (63 - __builtin_clzll((n))) #define BIT(n, i) (((n) >> (i)) & 1ll) #define MASK(i) (1ll << (i)) #define FLIP(n, i) ((n) ^ (1ll << (i))) #define ON(n, i) ((n) | MASK(i)) #define OFF(n, i) ((n) & ~MASK(i)) #define Int __int128 #define fi first #define se second typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef pair<long long, int> pli; typedef pair<int, long long> pil; typedef vector<pair<int, int>> vii; typedef vector<pair<long long, long long>> vll; typedef vector<pair<long long, int>> vli; typedef vector<pair<int, long long>> vil; template <class T1, class T2> bool maximize(T1 &x, T2 y) { if (x < y) { x = y; return true; } return false; } template <class T1, class T2> bool minimize(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } template <class T> void remove_duplicate(vector<T> &ve) { sort (ve.begin(), ve.end()); ve.resize(unique(ve.begin(), ve.end()) - ve.begin()); } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); template <class T> T random(T l, T r) { return uniform_int_distribution<T>(l, r)(rng); } template <class T> T random(T r) { return rng() % r; } const int N = 100; const int MOD = 1e9 + 7; const int inf = 1e9; const long long INF = 1e18; int B[N], R[N]; int ans[N]; #ifdef hwe namespace Jury { int dp[N][205], cnt[N][205]; int perm[N]; int W = 100; void test() { iota(perm, perm + N, 1); shuffle(perm, perm + N, rng); for (int i = 0; i < N; ++i) cerr << perm[i] << ' '; cerr << '\n'; } void umax(int i, int j, int u, int v, int val) { if (maximize(dp[i][j], dp[u][v] + val)) cnt[i][j] = cnt[u][v] + 1; if (dp[i][j] == dp[u][v] + val) maximize(cnt[i][j], cnt[u][v] + 1); } void playRound(int *B, int *R) { for (int j = 0; j <= B[0]; ++j) dp[0][j] = cnt[0][j] = 0; for (int j = B[0] + 1; j <= W; ++j) dp[0][j] = perm[0], cnt[0][j] = 1; for (int i = 1; i < N; ++i) { // use B[i] + 1 get perm[i] for (int j = 0; j <= W; ++j) { dp[i][j] = dp[i - 1][j]; cnt[i][j] = cnt[i - 1][j]; if (j > 0) umax(i, j, i, j - 1, 0); } for (int j = W; j >= B[i] + 1; --j) { umax(i, j, i - 1, j - (B[i] + 1), perm[i]); } } for (int i = N - 1, j = W; i >= 0; --i) { if (i == 0) { if (j > 0) R[i] = B[i] + 1; else R[i] = 0; } else { if (dp[i][j] == dp[i - 1][j - (B[i] + 1)] + perm[i] && cnt[i][j] == cnt[i - 1][j - (B[i] + 1)] + 1) { R[i] = B[i] + 1; j -= B[i] + 1; } else R[i] = 0; } } } } void playRound(int *B, int *R) { Jury::playRound(B, R); } #endif vector<int> play(const vector<int> &veB) { for (int i = 0; i < veB.size(); ++i) B[i] = veB[i]; playRound(B, R); vector<int> veR(veB.size()); for (int i = 0; i < veB.size(); ++i) veR[i] = R[i]; return veR; } int minValue(int n, int W) { // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. vector<int> B(n, 0); B[0] = 1; vector<int> R = play(B); if (R[0] <= B[0]) return 0; for (int i = 1; i < n; ++i) if (R[i] == 0) { return i; } return -1; } int maxValue(int n, int W) { // TODO: Implement Subtask 2 solution here. // You may leave this function unmodified if you are not attempting this // subtask. vector<int> candidates(n); iota(candidates.begin(), candidates.end(), 0); while (candidates.size() > 1) { vector<int> B(n, 0); for (auto &x : candidates) B[x] = W / candidates.size(); vector<int> R = play(B), new_candidates; for (auto &x : candidates) if (R[x] > B[x]) { new_candidates.emplace_back(x); } swap(candidates, new_candidates); } return candidates[0]; } int greaterValue(int n, int W) { // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. // Nếu B[0] = B[1] = 9 thì không thể lấy được cả 2 thằng này int low = 1, high = 9; while (low <= high) { int mid = (low + high) >> 1; vector<int> B(n, 0); B[0] = B[1] = mid; vector<int> R = play(B); bool isTake0 = R[0] > B[0], isTake1 = R[1] > B[1]; if (isTake0 != isTake1) return isTake1; if (isTake0) low = mid + 1; else high = mid - 1; } return -1; } void dnc(int n, int W, int *P, int l, int r, vector<int> &ve) { if (l == r) { P[ve[0]] = l; return; } int stone = (W == 2 * n ? W / (r - l + 1) : min(int(sqrt(2 * l)), W / (r - l + 1))); vector<int> B(n, 0); for (auto &x : ve) B[x] = stone; vector<int> R = play(B); vector<int> less, greater; for (auto &x : ve) { if (R[x] > B[x]) greater.emplace_back(x); else less.emplace_back(x); } dnc(n, W, P, l, l + less.size() - 1, less); dnc(n, W, P, r - greater.size() + 1, r, greater); } void allValues(int n, int W, int *P) { vector<int> ve(n); iota(ve.begin(), ve.end(), 0); dnc(n, W, P, 1, n, ve); } #ifdef hwe signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Jury::test(); allValues(N, Jury::W, ans); for (int i = 0; i < N; ++i) cerr << ans[i] << ' '; cerr << '\n'; cerr << '\n'; return 0; } #endif
#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...