| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 931915 | Lobo | The Big Prize (IOI17_prize) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
map<int,pair<int,pair<int,int>>> qr;
int cnt = 0;
int cntnonlol;
int n;
pair<int,pair<int,int>> query(int i) {
if(i == n) return mp(cntnonlol,mp(cntnonlol,0));
if(qr.count(i)) return qr[i];
++cnt;
vector<int> perg = ask(i);
return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}
int find_best(int N) {
n = N;
if(n <= 5000) {
for(int i = 0; i < n; i++) {
if(query(i).fr == 0) return i;
}
}
int S = n/420;
queue<pair<int,int>> q;
for(int i = 0; i*S < n; i++) {
// i*S,(i+1)*S
int l = i*S;
int r = min(n-1,(i+1)*S);
q.push(mp(l,r));
}
while(q.size()) {
int l = q.top().fr;
int r = q.top().sc;
q.pop();
if(l > r) continue;
if(query(l).fr == 0) return l;
if(query(r).fr == 0) return r;
if(r-l+1 <= 2) continue;
if(query(l) == query(r)) continue;
int mid = (l+r)/2;
q.push(mp(l,mid));
q.push(mp(mid,r));
// int ml = (2*l+r)/3;
// int mr = (l+2*r)/3;
// q.push(mp(l,ml));
// q.push(mp(ml,mr));
// q.push(mp(mr,r));
}
assert(false);
return -1;
}