| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1048259 | pcc | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,tree_order_statistics_node_update>;
#define pii pair<int,int>
#define fs first
#define sc second
#ifdef LOCAL
const int lim = 3;
const int sq = 5;
#else
const int lim = 5000;
const int sq = 500;
#endif
const int mxn = 2e5+10;
pii dp[mxn];
int N;
int big = 1e9;
int ans = 0;
bool done = false;
int C = 0;
ordered_set<int> st;
pii req(int p){
if(dp[p].fs != -1)return dp[p];
C++;
assert(C<=10000);
auto re = ask(p);
return (dp[p] = pii(re[0],re[1]));
}
int check(int p){
auto re = req(p);
if(!re.fs&&!re.sc)return 0;
else if(N-re.fs-re.sc == big)return 2;
else{
st.insert(p);
return 1;
}
}
void dfs(int l,int r){
if(done)return;
cerr<<"DFS: "<<l<<','<<r<<endl;
while(l<=r){
if(!check(l)){
ans = l;
done = true;
return;
}
else if(check(l) == 1){
l++;
}
else break;
}
while(l<=r){
if(!check(r)){
ans = r;
done = true;
return;
}
else if(check(r) == 1){
r--;
}
else break;
}
if(l>=r)return;
int cnt = req(r).fs+req(l).sc-(N-big);
if(!cnt)return;
cerr<<"CHECK: "<<l<<','<<r<<','<<cnt<<endl;
assert(cnt>0);
int mid = (l+r)>>1;
if(check(mid) == 0){
ans = mid;
done = true;
return;
}
if(l == r)return;
dfs(l,mid);
dfs(mid,r);
return;
}
int find_best(int nn) {
N = nn;
int pt = 0;
for(int i = 1;i*i<2e5;i++)pt = i;
cerr<<pt<<endl;
for(auto &i:dp)i = pii(-1,-1);
if(N<=lim){
for(int i = 0;i<N;i++){
auto tmp = req(i);
if(!tmp.fs&&!tmp.sc)return i;
}
assert(false);
return 0;
}
for(int i = 0;i<sq;i++){
auto tmp = req(i);
big = min(big,N-tmp.fs-tmp.sc);
}
cerr<<"BIG: "<<big<<endl;
dfs(0,N-1);
if(!done)exit(0);
return ans;
}