| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 407690 | Kevin_Zhang_TW | The Big Prize (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "prize.h"
const int MAX_N = 300010;
vector<int> qry(int id) {
static vector<int> mem[MAX_N];
if (mem[id].size()) return mem[id];
return mem[id] = ask(id);
}
int sum(int id) {
return qry(id)[0] + qry(id)[1];
}
int find_best(int n) {
bit T(n);
int cnt = 1, m, h;
bool bg = false;
while (h < n) {
while (sum(h) < cnt) {
if (sum(h) == 0) return h;
++h;
}
cnt = sum(h);
int l = h, r = n-1, m;
while (l < r) {
m = (l + r >> 1)+1;
if (sum(m) > cnt) {
cnt = sum(m);
break;
}
if (sum(m) < cnt || qry(m)[0] > qry(h)[0])
r = m-1;
else
l = m;
}
if (sum(h) != cnt) continue;
h = l + 1;
}
assert(false);
}