Submission #403803

#TimeUsernameProblemLanguageResultExecution timeMemory
403803yoavLKoala Game (APIO17_koala)C++14
33 / 100
84 ms328 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <queue> #include <stack> #include <bitset> #include <math.h> #include <fstream> #include <iomanip> #include "koala.h" using namespace std; using ll = int; using ld = long double; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vvvvll = vector<vvvll>; using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>; using vld = vector<ld>; using vstr = vector<string>; using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>; using pb = pair<bool, bool>; using vpb = vector<pb>; using vvpb = vector<vpb>; using vi = vector<int>; using vvi = vector<vi>; const ll mod = (ll)1e9 + 7; const ll inf = (ll)1e18; #define F first #define S second #define FAST ios_base::sync_with_stdio(0) #define FASTIN cin.tie(0) #define FASTOUT cout.tie(0) #define upmin(a, b) a = min(a, b) #define upmax(a, b) a = max(a, b) #define whatvec(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl; #define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl; #define wpr(x) cout << #x << " = " << (x) << endl; #define wprv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl; #define what(x) cout << #x << " = " << (x) << "\n"; #define pr(x) cout <<x << endl; #define rep(i,s,e) for(ll i = s;i < e; i++) #define all(x) x.begin(),x.end() #define pb push_back const ll len = 100; const ll maxcap = 8; ll a[len], b[len]; void fill(ll ind) { for (ll i = 0; i < len; i++) a[i] = 0; a[ind] = 1; } void pra() { pr("a:"); rep(i, 0, len) { cout << a[i] << " "; } cout << endl; } void prb() { pr("b:"); rep(i, 0, len) { cout << b[i] << " "; } cout << endl; } int minValue(int N, int W) { //pr("here"); // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. ll n = N, w = W; //vll a(n, 1); fill(0); rep(i, 0, len) b[i] = -1; bool ok = false; playRound(a, b); rep(i, 0, len) if (b[i] != -1) ok = true; if (!ok) while (true); for (ll i = 0; i < len; i++) { if (b[i] == 0) return i; } fill(1); playRound(a, b); rep(i, 0, len) { if (b[i] == 0) return i; } while (true); return 0; } int rec(vll ind) { if (ind.size() == 1) { return ind[0]; } ll sz = ind.size(); ll cap = len / sz; rep(i, 0, len) { a[i] = 0; } rep(i, 0, sz) { a[ind[i]] = cap; } /* pr("a:"); rep(i, 0, len) { cout << a[i] << " "; } cout << endl; */ playRound(a, b); /* pr("b:"); rep(i, 0, len) { cout << b[i] << " "; } cout << endl; */ ll maxv = 0; rep(i, 0, len) { upmax(maxv, b[i]); } vll nind; rep(i, 0, len) { if (b[i] == maxv) nind.push_back(i); } return rec(nind); } 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. vll ind; for (ll i = 0; i < len; i++) ind.push_back(i); return rec(ind); } int put_v(ll v) { //wpr(v); rep(i, 0, len) { a[i] = 0; } a[0] = a[1] = v; playRound(a, b); //prb(); if (b[0] > b[1]) return 0; if (b[0] < b[1]) return 1; if (b[0] > 0) return 2; return 3; } int put_v_comp(ll v, ll i1, ll i2) { //wpr(v); rep(i, 0, len) { a[i] = 0; } a[i1] = a[i2] = v; //pra(); playRound(a, b); //prb(); if (b[i1] > b[i2]) return 0; if (b[i1] < b[i2]) return 1; if (b[i1] > 0) return 2; return 3; } bool comp(const ll i, const ll j) { //cout << "comp: " << i << ", " << j << endl; if (i == j) return false; //return false; ll low = 1, high = maxcap, mid; while (low <= high) { mid = (low + high) / 2; ll res = put_v_comp(mid, i, j); //wpr(res); if (res <= 1) { //cout << "returning: " << res << endl; return res; } if (res == 2) { low = mid + 1; } else { high = mid - 1; } } return false; } 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. return comp(0, 1); } void allValues(int N, int W, int* P) { //pr("wasup"); if (W == 2 * N && false) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. //pr("hii"); vll inds(len); for (ll i = 0; i < len; i++) { inds[i] = i; } sort(inds.begin(), inds.end(), comp); rep(i, 0, len) { P[i] = inds[i]+1; } } } /* 4 1 6 6 5 3 2 1 6 4 3 1 6 6 5 3 2 1 6 4 3 1 6 6 3 5 2 1 6 4 4 1 6 6 5 3 2 1 6 4 4 1 6 6 5 3 2 1 6 4 3 1 6 6 1 2 5 3 6 4 3 1 6 6 5 4 3 2 1 4 1 6 6 5 3 2 1 6 4 5 1 6 6 1 2 5 3 6 4 4 1 6 6 1 2 3 4 5 6 */

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:101:8: warning: unused variable 'n' [-Wunused-variable]
  101 |     ll n = N, w = W;
      |        ^
koala.cpp:101:15: warning: unused variable 'w' [-Wunused-variable]
  101 |     ll n = N, w = W;
      |               ^
#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...