이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 = 100;
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;
}
컴파일 시 표준 에러 (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |