| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 137797 | MAMBA | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
map<int , vi> mp;
inline vi F(int i) {
if (mp.count(i)) return mp[i];
if (mp.size() + 1 > 10000) assert(0);
return (mp[i] = ask(i));
}
inline int sum(vi me) {
return accumulate(all(me) , 0);
}
int least, ans;
bitset<400000> mark;
void solve(int l , int r, int le , int ri) {
if (ans != -1) return;
if (l >= r) return;
if (le + ri == least) return;
int mid = l + r >> 1;
bool happy = false;
rep(i , 0 , r - l) {
if (i & 1) mid -= i;
else mid += i;
vi me = F(mid);
mark[mid] = true;
if (sum(me) == 0) ans = mid;
if (sum(me) == least) {
happy = true;
break;
}
if (le + ri + i == least) return;
}
if (!happy) return;
int ptr = l;
while (!mark[ptr]) ptr++;
int ptr2 = ptr;
while (sum(F(ptr2)) != least) ptr2++;
int ptr3 = r - 1;
while (!mark[ptr3]) ptr3--;
int ptr4 = ptr3;
while (sum(F(ptr4)) != least) ptr4--;
solve(l , ptr , le , ptr2 - ptr + F(ptr2)[1]);
solve(ptr3 + 1 , r , ptr3 - ptr4 + F(ptr4)[0], ri);
}
int find_best(int n) {
mp.clear();
rep(i , 0 , n) mark[i] = false;
ltof = 0;
rtof= n;
least = -1; ans = -1;
for (int i = 1; (i - 2) * (i - 2) <= n; i++) {
least = max(least , sum(F(i - 1)));
if (sum(F(i - 1)) == 0) return i - 1;
}
solve(0 , n , 0 , 0);
return ans;
}