Submission #718770

#TimeUsernameProblemLanguageResultExecution timeMemory
718770pragmatistKoala Game (APIO17_koala)C++17
47 / 100
55 ms440 KiB
#include "koala.h" #include <bits/stdc++.h> #define sz(v) (int)v.size() #define pb push_back using namespace std; 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. int n = N; int a[n], b[n]; memset(a, 0, sizeof(a)); a[0] = 1; playRound(a, b); for(int i = 0; i < n; ++i) { if(b[i] == 0) { return i; } } 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. int n = N, a[n], b[n]; vector<int> v; for(int i = 0; i < n; ++i) { v.pb(i); } while(sz(v) > 1) { int t = W / sz(v); bool used[n]; memset(used, 0, sizeof(used)); for(auto x : v) used[x] = 1; for(int i = 0; i < n; ++i) { if(!used[i]) { a[i] = 0; } else { a[i] = t; } } playRound(a, b); vector<int> to; for(int i = 0; i < n; ++i) { if(b[i] > t) { to.pb(i); } } v = to; } return v[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 n = N, a[n], b[n]; int l = 1, r = min(9, W / 2), ans = -1; while(l <= r) { int mid = (l + r) >> 1; memset(a, 0, sizeof(a)); a[0] = a[1] = mid; playRound(a, b); if(a[0] >= b[0] && a[1] >= b[1]) { r = mid - 1; continue; } bool c = (a[0] < b[0]), d = (a[1] < b[1]); if(c && d) { l = mid + 1; continue; } ans = (c < d); break; } assert(ans != -1); return ans; } bool comp(int i, int j, int n) { int a[n], b[n]; memset(a, 0, sizeof(a)); a[i] = a[j] = n; playRound(a, b); assert((b[i] > a[i]) || (b[j] > a[j])); if(b[i] < a[i]) { return 1; } return 0; } void calc(int l, int r, vector<int> &v, vector<int> &temp) { if(l == r) { return; } int mid = (l + r) >> 1; calc(l, mid, v, temp); calc(mid + 1, r, v, temp); int timer = l, i = l, j = mid + 1; while(i <= mid && j <= r) { if(comp(v[i], v[j], sz(v))) { temp[timer++] = v[i++]; continue; } temp[timer++] = v[j++]; } for(int k = i; k <= mid; ++k) temp[timer++] = v[k]; for(int k = j; k <= r; ++k) temp[timer++] = v[k]; for(int i = l; i <= r; ++i) v[i] = temp[i]; } 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. int n = N; vector<int> v, p; for(int i = 1; i <= n; ++i) { v.pb(i - 1); } p = v; calc(0, n - 1, v, p); for(int i = 0; i < n; ++i) { P[v[i]] = i + 1; } } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. int n = N, a[n], b[n]; vector<int> v; for(int t = 0; t < n; ++t) { } for(int i = 0; i < n; ++i) { P[v[i]] = i + 1; } } }

Compilation message (stderr)

koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:137:14: warning: unused variable 'a' [-Wunused-variable]
  137 |   int n = N, a[n], b[n];
      |              ^
koala.cpp:137:20: warning: unused variable 'b' [-Wunused-variable]
  137 |   int n = N, a[n], b[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...