Submission #680693

#TimeUsernameProblemLanguageResultExecution timeMemory
680693QwertyPiKoala Game (APIO17_koala)C++14
100 / 100
78 ms340 KiB
#include "koala.h" #include <bits/stdc++.h> const int N = 100; using namespace std; int minValue(int N, int W) { int a[N], b[N]; a[0] = 1; for(int i = 1; i < N; i++){ a[i] = 0; } playRound(a, b); if(b[0] <= 1){ return 0; }else{ for(int i = 1; i < N; i++){ if(b[i] == 0){ return i; } } } } int getMax(int N, int W, vector<int> v){ int a[N], b[N]; int st = v.size(); while(v.size() != 1){ for(int i = 0; i < N; i++) a[i] = 0; int k = v.size(); int sq = 0; while((sq + 1) * (sq + 2) / 2 < st) sq++; for(auto i : v){ a[i] = min(st + W - N - 1, min(W / k, k + W - N + sq - 1)); } playRound(a, b); vector<int> nv; for(int i = 0; i < N; i++){ if(a[i] != 0 && b[i] > a[i]){ nv.push_back(i); } } assert(nv.size() != 0 && v.size() != nv.size()); v = nv; } return v[0]; } int maxValue(int N, int W) { vector<int> v; for(int i = 0; i < N; i++) v.push_back(i); return getMax(N, W, v); } int greaterValue(int N, int W) { int a[N], b[N]; for(int k : vector<int>{2, 5, 10}){ a[0] = a[1] = k; for(int i = 2; i < N; i++){ a[i] = 0; } playRound(a, b); if(b[0] == 0 && b[1] == 0){ return !minValue(N, W); } if(b[0] > k && k >= b[1]){ return 0; }else if(b[0] <= k && k < b[1]){ return 1; } } assert(1 == 0); } int C2(int n){ if(n <= 0) return 0; return n * (n + 1) / 2; } void solve(int L, int R, int *P, vector<int>& indexes){ if(L == R){ P[indexes[0]] = L; return; } int S = R - L + 1; for(int K = 1; ; K++){ if(C2(K + 1 - S) < R && L <= C2((K + 1) * S - S) - C2((K + 1) * (S - 1) - S)){ int a[N], b[N]; for(int i = 0; i < N; i++) a[i] = b[i] = 0; for(auto i : indexes) a[i] = K; playRound(a, b); vector<int> sm, gr; for(auto i : indexes) { if(b[i] > K) gr.push_back(i); else sm.push_back(i); } solve(L, L + sm.size() - 1, P, sm); solve(L + sm.size(), R, P, gr); break; } } } void allValues(int N, int W, int *P) { if(W == N * 2){ vector<int> Q; vector<int> v; for(int i = 0; i < N; i++){ v.push_back(i); } for(int i = 0; i < N; i++){ int mx = getMax(N, W, v); Q.push_back(mx); int idx = 0; for(int i = 0; i < N; i++){ if(v[i] == mx) idx = i; } swap(v[idx], v[(int) v.size() - 1]); v.resize(N - i - 1); } for(int i = 0; i < N; i++){ P[Q[i]] = N - i; } }else{ vector<int> indexes; for(int i = 0; i < N; i++){ indexes.push_back(i); } solve(1, N, P, indexes); } }

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
   23 | }
      | ^
#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...