Submission #1191054

#TimeUsernameProblemLanguageResultExecution timeMemory
1191054Zbyszek99The Big Prize (IOI17_prize)C++20
95.26 / 100
14 ms740 KiB
#include "prize.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; map<int,pii> queryMap; const int jump = 512; int n; pii query(int x) { if(queryMap.find(x) != queryMap.end()) { return queryMap[x]; } vi a = ask(x); queryMap[x] = {a[0],a[1]}; return {a[0],a[1]}; } int get_worst_sum() { int s = 0; rep(i,min(n,475)) { pii a = query(i); s = max(s,a.ff+a.ss); } return s; } int find_best(int N) { n = N; random_start(); int worst_sum = get_worst_sum(); int cur_poz = 0; while(cur_poz < n) { pii x = query(cur_poz); if(x.ff + x.ss == 0) return cur_poz; if(x.ff + x.ss != worst_sum) { cur_poz++; continue; } int poz2 = min(n-1,cur_poz+jump); pii x2 = query(poz2); if(x2.ff + x2.ss == 0) return poz2; if(x.ff == x2.ff && x.ss == x2.ss) { cur_poz = poz2+1; continue; } int l = cur_poz+1; int r = poz2-1; int ans = cur_poz; while(l <= r) { int mid = (l+r)/2; pii x2 = query(mid); if(x2.ff + x2.ss == 0) return mid; if(x2.ff == x.ff && x2.ss == x.ss) { ans = mid; l = mid+1; } else { r = mid-1; } } cur_poz = ans+1; } }

Compilation message (stderr)

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