# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1134940 | pokmui9909 | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
set<ll> S[200005];
ll L[200005];
ll dnc(ll l, ll r){
if(l > r) return -1;
ll m = (l + r) / 2;
auto t = ask(m);
ll v = t[0] + t[1];
if(v == 0) return m;
S[v].insert(m);
L[m] = t[0];
auto it = S[v].lower_bound(m);
if(it == S[v].begin() || L[*prev(it)] != L[m]){
ll f = dnc(l, m - 1);
if(f != -1) return f;
}
if(it == prev(S[v].end()) || L[*next(it)] != L[m]){
ll f = dnc(m + 1, r);
if(f != -1) return f;
}
return -1;
}