Submission #255354

#TimeUsernameProblemLanguageResultExecution timeMemory
255354Osama_AlkhodairyKoala Game (APIO17_koala)C++17
100 / 100
89 ms512 KiB
#include <bits/stdc++.h> #include "koala.h" //~ #include "grader.cpp" using namespace std; int n; vector <int> ans; bool cmp(int i, int j){ int B[n], R[n]; for(int i = 0 ; i < n ; i++){ B[i] = R[i] = 0; } int l = 1, r = 9; while(l <= r){ int mid = (l + r) / 2; B[i] = B[j] = mid; playRound(B, R); if((R[i] > B[i]) == (R[j] > B[j])){ if(R[i] > B[j]) l = mid + 1; else r = mid - 1; } else return R[j] > B[j]; } assert(false); } bool cmp2(int i, int j){ int B[n], R[n]; for(int i = 0 ; i < n ; i++){ B[i] = R[i] = 0; } B[i] = B[j] = 100; playRound(B, R); return R[j] > B[j]; } int calc(int l, int r, int g){ int mx = 0, mx_ret = 0; for(int i = 0 ; i <= n - (r - l + 1) ; i++){ int cur_ops = n; int cur_sum = 0; int f = i; int cur_pos = n; while(f > 0){ if(l <= cur_pos && cur_pos <= r){ cur_pos--; continue; } if(cur_pos <= 0) break; f--; cur_sum += cur_pos; cur_pos--; cur_ops--; } cur_pos = r; int cur_ret = 0; while(l <= cur_pos){ if(g + 1 > cur_ops) break; cur_sum += cur_pos; cur_pos--; cur_ops -= g + 1; cur_ret++; } if(cur_sum >= mx){ mx = cur_sum; mx_ret = cur_ret; } } return mx_ret; } void solve(int l, int r, vector <int> cur){ if(r < l) return; if(l == r){ ans[cur[0]] = l; return; } int opt = (r - l + 1) / 2; int best_i = 0, best = calc(l, r, 0); for(int i = 0 ; i <= 100 ; i++){ int cur = calc(l, r, i); if(abs(opt - cur) < abs(opt - best)){ best = cur; best_i = i; } } int B[n], R[n]; for(int i = 0 ; i < n ; i++){ B[i] = R[i] = 0; } for(auto &i : cur){ B[i] = best_i; } playRound(B, R); vector <int> s, e; for(auto &i : cur){ if(R[i] > B[i]) e.push_back(i); else s.push_back(i); } solve(l, l + (int)s.size() - 1, s); solve(r - (int)e.size() + 1, r, e); } int minValue(int N, int W) { n = N; int B[n], R[n]; for(int i = 0 ; i < n ; i++){ B[i] = R[i] = 0; } B[0]++; playRound(B, R); for(int i = 0 ; i < n ; i++){ if(B[i] >= R[i]) return i; } return 0; } int maxValue(int N, int W) { n = N; int B[n], R[n]; vector <int> cands; for(int i = 0 ; i < n ; i++){ cands.push_back(i); } while(cands.size() > 1){ for(int i = 0 ; i < n ; i++){ B[i] = R[i] = 0; } int cur = W / cands.size(); for(auto &i : cands) B[i] = cur; playRound(B, R); cands.clear(); for(int i = 0 ; i < n ; i++){ if(B[i] == cur && R[i] > B[i]){ cands.push_back(i); } } } return cands[0]; } int greaterValue(int N, int W) { n = N; if(cmp(0, 1)) return 1; return 0; } void allValues(int N, int W, int *P) { n = N; if (W == 2*N) { vector <int> all; for(int i = 0 ; i < n ; i++){ all.push_back(i); } stable_sort(all.begin(), all.end(), cmp2); for(int i = 0 ; i < n ; i++){ P[all[i]] = i + 1; } } else { ans.resize(n); vector <int> all; for(int i = 0 ; i < n ; i++){ all.push_back(i); } solve(1, n, all); for(int i = 0 ; i < n ; i++){ P[i] = ans[i]; } } }
#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...