Submission #593842

#TimeUsernameProblemLanguageResultExecution timeMemory
593842AlperenTThe Big Prize (IOI17_prize)C++17
98.05 / 100
70 ms1068 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int int_rand(int a, int b){ return uniform_int_distribution<int>(a, b)(rng); } const int TRYMAX = 450, K = 1200, DIFF = 10000; int maxcnt = 0; map<int, vector<int>> mp; vector<int> query(int pos){ if(mp.find(pos) == mp.end()) mp[pos] = ask(pos); return mp[pos]; } int find_best(int n){ set<int> st; while(st.size() < n && st.size() < TRYMAX) st.insert(int_rand(0, n - 1)); for(auto i : st){ vector<int> vec = query(i); maxcnt = max(maxcnt, vec[0] + vec[1]); } vector<bool> ismax(n, false); int pos = 0, prefix = 0; while(pos < n){ vector<int> vec = query(pos); if(vec[0] + vec[1] != maxcnt){ pos++; continue; } int l = pos - 1, r = min(pos + K, n); while(r - l > 1){ int m = l + (r - l) / 2; auto it = mp.lower_bound(m); int m2 = m; if(it != mp.end()){ if(it->first > l && it->first < r && abs(it->first - m) <= DIFF) m2 = it->first; } if(it != mp.begin()){ if(prev(it)->first > l && prev(it)->first < r && abs(prev(it)->first - m) <= DIFF) m2 = prev(it)->first; } m = m2; vector<int> vec = query(m); if(vec[0] + vec[1] == maxcnt && (m + 1 - vec[0]) - prefix == m - pos + 1) l = m; else r = m; } prefix += (l - pos + 1); for(int i = pos; i <= l; i++) ismax[i] = true; pos = max(pos + 1, l + 1); } for(int i = 0; i < n; i++){ if(!ismax[i]){ vector<int> vec = query(i); if(vec[0] + vec[1] == 0) return i; } } return -1; }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:27:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  while(st.size() < n && st.size() < TRYMAX) st.insert(int_rand(0, n - 1));
      |        ~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...