| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1080488 | TB_ | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
typedef vector<ll> vl;
typedef vector<vl> vvl;
int find_best(int n);
// std::vector<int> ask(int i);
std::vector<int> ask(int i){
ll gaah = 2;
if(i==gaah) return {0, 0};
else if(i>gaah) return {1, 0};
else return {0, 1};
}
ll valval = 1;
struct Node{
Node *lnode, *rnode;
ll l, r, val = valval;
Node(ll l, ll r) : l(l), r(r){
if(r-l>1){
ll mid = (r+l) / 2;
lnode = new Node(l, mid);
rnode = new Node(mid, r);
val = lnode->val+rnode->val;
}
}
void update2(ll lo, ll hi){
if(r <= lo || hi <= l) return;
if(r <= hi && lo <= l){
val = 1;
return;
}
lnode->update2(lo, hi);rnode->update2(lo, hi);
val = lnode->val+rnode->val;
}
ll sumQuery(ll lo, ll hi){
if(r <= lo || hi <= l) return 0;
if(r <= hi && lo <= l) return val;
return lnode->sumQuery(lo, hi)+rnode->sumQuery(lo, hi);
}
ll query(ll x){
if(r-l == 1){
val = 0;
return l;
}
ll res;
if(lnode->val>x) res = lnode->query(x);
else{
x-=lnode->val;
res = rnode->query(x);
}
val = lnode->val+rnode->val;
return res;
}
};
int find_best(int n){
ll prething = -1;
mt19937 rng(42);
fo(i, 500){
ll temp = rng()%n;
vector<int> res = ask(temp);
if(res[0] ==0 && res[1] == 0){
return temp;
}
prething = max(prething, (ll)res[0]+res[1]);
}
Node st(0, n);
valval = 0;
Node st2(0, n);
while(1){
ll lo = 0;
ll hi = n;
while(hi-lo>1){
ll mid = (hi+lo) / 2;
ll a = st.sumQuery(0, lo);
ll b = st.sumQuery(0, hi);
ll pos = st.query((a+b)/2);
vector<int> res = ask(mid);
if(res[0] ==0 && res[1] == 0){
return mid;
}
if(res[0]+res[1] <prething){
st2.update2(pos, pos+1);
break;
}
res[0]-=st2.sumQuery(0, pos);
if(res[0]) hi = mid;
else lo = mid+1;
}
return lo;
}
}