Submission #200843

#TimeUsernameProblemLanguageResultExecution timeMemory
200843BTheroKoala Game (APIO17_koala)C++17
43 / 100
111 ms504 KiB
// Why am I so dumb? :c // chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> #include "koala.h" //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; //template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int n, w; int minValue(int N, int W) { int me[N], you[N]; for (int i = 0; i < N; ++i) { me[i] = 0; } me[0] = 1; playRound(me, you); int i = 0; while (you[i]) { ++i; } return i; } int maxValue(int N, int W) { int me[N], you[N]; vector<int> v; for (int i = 0; i < N; ++i) { v.pb(i); } while (v.size() > 1) { int sz = v.size(); int k = (W + sz) / sz - 1; fill(me, me + N, 0); // v.size() > k for (int x : v) { me[x] = k; } playRound(me, you); vector<int> nv; for (int x : v) { if (you[x] > me[x]) { nv.pb(x); } } assert(!nv.empty()); v = nv; } return v[0]; } bool cmp(int a, int b) { int me[n] = {}, you[n]; int L = 1, R = 8; while (L <= R) { int x = (L + R) >> 1; me[0] = me[1] = x; playRound(me, you); if (you[a] != you[b]) { if (you[a] > you[b]) { return 0; } else { return 1; } } if (you[a] > 0) { L = x + 1; } else { R = x - 1; } } } bool cmp2(int a, int b) { int me[n] = {}, you[n]; me[a] = me[b] = n; playRound(me, you); return you[b] > me[b]; } int greaterValue(int N, int W) { n = N; w = W; return cmp(0, 1) ? 1 : 0; } vector<int> solve(vector<int> v, int lim) { if (v.size() <= 1) { return v; } if (v.size() > lim) { stable_sort(all(v), cmp); return v; } int me[n] = {}, you[n]; int k = w / v.size(); for (int x : v) { me[x] = k; } playRound(me, you); vector<int> a, b; for (int x : v) { if (you[x] > k) { b.pb(x); } else { a.pb(x); } } a = solve(a, lim - 1); b = solve(b, lim - 1); for (int x : b) { a.pb(x); } return a; } void allValues(int N, int W, int *P) { n = N; w = W; vector<int> v; for (int i = 0; i < n; ++i) { v.pb(i); } if (w == 2 * n) { stable_sort(all(v), cmp2); } else { v = solve(v, n); } for (int i = 0; i < v.size(); ++i) { P[v[i]] = i + 1; } }

Compilation message (stderr)

koala.cpp: In function 'std::vector<int> solve(std::vector<int>, int)':
koala.cpp:125:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (v.size() > lim) {
         ~~~~~~~~~^~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:175:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i) {
                     ~~^~~~~~~~~~
koala.cpp: In function 'bool cmp(int, int)':
koala.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...