| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 119853 | TuGSGeReL | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
int a[200001], ans = -1;
vector <int> resl, resr;
void solve(int l, int r) {
if ( ans != -1 || l >= r )
return;
resl = ask(l);
resr = ask(r);
if ( resl[0] + resl[1] == 0 ) {
ans = l;
return;
}
if ( resr[0] + resr[1] == 0 ) {
ans = r;
return;
}
if (resl[0] + resl[1] < resr[0] + resr[1]) {
solve(l + 1, r);
return;
}
if (resl[0] + resl[1] > resr[0] + resr[1]) {
solve(l, r - 1);
return;
}
if ( resl[0] == resr[0] )
return;
int mid = (l + r) / 2;
solve(l, mid);
solve(mid, r);
}
int find_best(int n) {
int idx = -1;
for (int i = 0; i < min(n, 500); i++) {
vector <int> res = ask(i);
if ( res[0] + res[1] == 0 )
return i;
if ( res[0] + res[1] > mx ) {
mx = res[0] + res[1];
idx = i;
}
}
solve(idx, n - 1);
return ans;
}