Submission #523273

#TimeUsernameProblemLanguageResultExecution timeMemory
523273valerikkKoala Game (APIO17_koala)C++17
100 / 100
75 ms444 KiB
#include "koala.h" #include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <cstring> #include <functional> using namespace std; int B[100], R[100]; 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. memset(B, 0, sizeof(B)); B[0] = 1; playRound(B, R); for (int i = 0; i < N; ++i) { if (R[i] == 0) { return i; } } assert(false); return 0; } 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> cur; for (int i = 0; i < N; ++i) { cur.push_back(i); } while (cur.size() != 1) { int x = W / (int)cur.size(); memset(B, 0, sizeof(B)); for (int i : cur) { B[i] = x; } playRound(B, R); vector<int> ncur; for (int i : cur) { if (R[i] > B[i]) { ncur.push_back(i); } } cur = ncur; } return cur[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. int l = 1, r = min(N / 2, 9); int res = -1; while (r - l > 1) { int m = (l + r) / 2; memset(B, 0, sizeof(B)); B[0] = B[1] = m; playRound(B, R); if ((B[1] < R[1]) != (B[0] < R[0])) { res = B[1] < R[1]; } if (B[0] < R[0] || B[1] < R[1]) { l = m + 1; } else { r = m - 1; } } if (res == -1) { memset(B, 0, sizeof(B)); B[0] = B[1] = l; playRound(B, R); res = B[1] < R[1]; } return res; } void allValues(int N, int W, int *P) { if (W == 2*N) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. auto cmp = [&](int a, int b) { memset(B, 0, sizeof(B)); B[a] = B[b] = N; playRound(B, R); return R[b] > B[b]; }; vector<int> sorted(N); for (int i = 0; i < N; ++i) { sorted[i] = i; } stable_sort(sorted.begin(), sorted.end(), cmp); for (int i = 0; i < N; ++i) { *(P + sorted[i]) = i + 1; } } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. auto check = [&](int l, int r, int x) { vector<int> a, b; for (int i = 1; i <= N; ++i) { if (l <= i && i <= r) { a.push_back(i); } else { b.push_back(i); } } sort(a.rbegin(), a.rend()); sort(b.rbegin(), b.rend()); int sz_a = a.size(), sz_b = b.size(); vector<int> pref_a(sz_a + 1, 0); for (int i = 0; i < sz_a; ++i) { pref_a[i + 1] = pref_a[i] + a[i]; } vector<int> pref_b(sz_b + 1, 0); for (int i = 0; i < sz_b; ++i) { pref_b[i + 1] = pref_b[i] + b[i]; } vector<pair<int, int>> keks; for (int take_a = 0; take_a <= sz_a && take_a * (x + 1) <= W; ++take_a) { int take_b = min(sz_b, W - take_a * (x + 1)); keks.push_back({pref_a[take_a] + pref_b[take_b], take_a}); } sort(keks.rbegin(), keks.rend()); for (auto kek : keks) { if (kek.first == keks[0].first && (kek.second == 0 || kek.second == sz_a)) { return false; } } return true; }; function<void(vector<int>, int, int)> rec = [&](vector<int> guys, int l, int r) { if (guys.size() == 1) { *(P + guys[0]) = l; return; } for (int x = 0; x * (r - l + 1) <= W; ++x) { if (check(l, r, x)) { memset(B, 0, sizeof(B)); for (int i : guys) { B[i] = x; } playRound(B, R); vector<int> small, big; for (int i : guys) { if (B[i] < R[i]) { big.push_back(i); } else { small.push_back(i); } } rec(small, l, l + (int)small.size() - 1); rec(big, r - (int)big.size() + 1, r); return; } } assert(false); }; vector<int> guys; for (int i = 0; i < N; ++i) { guys.push_back(i); } rec(guys, 1, N); } }
#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...