Submission #122589

#TimeUsernameProblemLanguageResultExecution timeMemory
122589tselmegkhThe Big Prize (IOI17_prize)C++14
0 / 100
1482 ms1048576 KiB
#include<bits/stdc++.h> #include "prize.h" using namespace std; #define INF 1e9 #define MAX 100005 #define xx first #define yy second #define pb push_back #define mp make_pair #define ull long long #define FOR(i,a,b) for(int i=a;i<=b;i++) #define nl '\n' #define zai <<' '<< #define all(a) a.begin(),a.end() #define pc __builtin_popcount #define debug(args...) cerr << #args << " = "; Dbg,args; cerr << nl; struct Dbg { template<typename T> Dbg& operator,(const T& v) { cerr << v << ", "; return *this; } } Dbg; template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){ if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;} typedef vector<int> vi; typedef pair<int,int> ii; typedef vector<ii> vii; template<class C> void mini(C &_a, C _b) { _a = min(_a, _b); } template<class C> void maxi(C &_a, C _b) { _a = max(_a, _b); } struct val{ int L, R; }; map<int, val> mymap; int mx = 0; vii possiblities; val optimized_ask(int i){ if(mymap.find(i) == mymap.end()){ vector<int> tmp = ask(i); val q; q.L = tmp[0]; q.R = tmp[1]; return mymap[i] = q; } else{ return mymap[i]; } } void solve(int l, int r, val LV, val RV){ if(l > r)return; if(l == r){ possiblities.pb({LV.L + LV.R, l}); return; } int mid = (l + r) >> 1; val MV = optimized_ask(mid); if(MV.L + MV.R != mx){ possiblities.pb({MV.L + MV.R,mid}); solve(l, mid - 1, LV, optimized_ask(mid - 1)); solve(mid + 1, r, optimized_ask(mid + 1), RV); } else{ solve(l, mid, LV, MV); solve(mid, r, MV, RV); } } int find_best(int n){ val first = optimized_ask(0); mx = first.L + first.R; if(mx == 0)return 0; solve(0, n - 1, optimized_ask(0), optimized_ask(n - 1)); for(auto x : possiblities){ if(x.first == 0){ return x.second; } } }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...