Submission #557686

#TimeUsernameProblemLanguageResultExecution timeMemory
557686nutellaKoala Game (APIO17_koala)C++17
100 / 100
53 ms460 KiB
#include "koala.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxN = 100; int B[maxN], R[maxN]; void cl() { memset(B, 0, sizeof(B)); memset(R, 0, sizeof(R)); } 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. cl(); B[0] = 1; playRound(B, R); if (R[0]) { return int(min_element(R, R + N) - R); } else { return 0; } } int maxValue(int N, int W) { // return i such as P[i] = n vector<int> left(N); iota(begin(left), end(left), 0); while (size(left) > 1) { int x = W / (int) size(left); cl(); for (int i: left) B[i] = x; playRound(B, R); vector<int> tmp; for (int i: left) if (B[i] < R[i]) tmp.push_back(i); swap(tmp, left); } assert(size(left) == 1); return left[0]; } int greaterValue(int N, int W) { // compare P[0] and P[1] int l = 0, r = W / 8; while (l + 1 < r) { int m = (l + r) >> 1; cl(); B[0] = B[1] = m; playRound(B, R); bool took1 = R[0] > B[0]; bool took2 = R[1] > B[1]; if (took1 && took2) l = m; else if (!took1 && !took2) r = m; else if (took1) return 0; else return 1; } return 0; } void allValues(int N, int W, int *P) { if (W == N) { vector<int> ord(N); iota(begin(ord), end(ord), 0); function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> v) { if (l + 1 == r) { P[v[0]] = l; } else { int x = min((int)sqrt(l * 2), W / (r - l)); cl(); for (int i : v) { B[i] = x; } playRound(B, R); vector<int> small, big; for (int i : v) { if (R[i] > B[i]) { big.push_back(i); } else { small.push_back(i); } } int mid = l + int(size(small)); solve(l, mid, small), solve(mid, r, big); } }; solve(1, N + 1, ord); } else { vector<int> ord(N); iota(begin(ord), end(ord), 0); stable_sort(begin(ord), end(ord), [&](int i, int j) { cl(); B[i] = N, B[j] = N; playRound(B, R); return B[i] >= R[i]; }); for (int i = 0; i < N; ++i) P[ord[i]] = i + 1; } }
#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...