| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1198952 | dosts | 커다란 상품 (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
const int inf = 2e9;
map<int,vi> cache;
int asked = 0;
vi myask(int p) {
if (cache.count(p)) return cache[p];
asked++;
return cache[p] = ask(p);
}
int find_best(int n) {
set<int> possible;
int mx = 0;
srand(time(0));
int select;
for (int i = 0;i<450 && i<n;i++) {
vi v = myask(i);
if (v[0]+v[1] == 0) return 0;
if (v[0]+v[1] > mx) {
mx = v[0]+v[1];
select = i;
}
}
for (int i=0;i<n;i++) possible.insert(i);
int pl = select,pr = select;
while (possible.size() >= 5000-asked) {
if (pl <= 0) break;
vector<int> q = myask(pl);
vi prv = myask(pl-1);
if ((prv[0]+prv[1]) != (q[0]+q[1])) {
int ptr = pl-1;
while (ptr > 0) {
prv = myask(ptr-1);
if (prv[0]+prv[1] == 0) return ptr-1;
if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr--;
else break;
}
pl = ptr-1;
continue;
}
int l = 0;
int r = pl-1;
while (l<=r) {
int m = (l+r) >> 1;
vi vv = myask(m);
if (vv[0]+vv[1] == 0) return m;
if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[1] > q[1])) l = m+1;
else r = m-1;
}
for (int j = pl;j >= l;j--) possible.erase(j);
pl = l;
}
while (possible.size() >= 5000-asked) {
if (pr >= n-1) break;
vector<int> q = myask(pr);
vi prv = myask(pr+1);
if ((prv[0]+prv[1]) != (q[0]+q[1])) {
int ptr = pr+1;
while (ptr < n-1) {
prv = myask(ptr+1);
if (prv[0]+prv[1] == 0) return ptr-1;
if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr++;
else break;
}
pr = ptr+1;
continue;
}
int l = pr+1;
int r = n-1;
while (l<=r) {
int m = (l+r) >> 1;
vi vv = myask(m);
if (vv[0]+vv[1] == 0) return m;
if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[0] > q[0])) r = m-1;
else l = m+1;
}
for (int j = pr;j <= r;j++) possible.erase(j);
pr = r;
}
vi v;
for (auto it : possible) v.push_back(it);
random_shuffle(all(v),mt19937_64(0));
for (auto it : v) {
vi vv = myask(it);
if (vv[0] + vv[1] == 0) return it;
}
assert(0);
}