| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 593046 | Tekor | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 2e5 + 10;
int k,mx,kol;
vector <int> was[N];
bool u[N];
vector <pii> q;
int t[N * 4],t1[N * 4];
void build(int v,int tl,int tr) {
if(tl == tr) {
t[v] = 1;
t1[v] = 0;
return;
}
int tm = (tl + tr) / 2;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v] = t[v + v] + t[v + v + 1];
}
int get(int v,int tl,int tr,int x) {
if(tl == tr)return tl;
int tm = (tl + tr) / 2;
if(t[v + v] >= x)return get(v + v,tl,tm,x);
else return get(v + v + 1,tm + 1,tr,x - t[v + v]);
}
void upd(int v,int tl,int tr,int pos) {
if(tl == tr) {
t[v] = 0;
t1[v] = 1;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)upd(v + v,tl,tm,pos);
else upd(v + v + 1,tm + 1,tr,pos);
t[v] = t[v + v] + t[v + v + 1];
t1[v] = t1[v + v] + t1[v + v + 1];
}
int get1(int v,int tl,int tr,int l,int r) {
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r)return t1[v];
int tm = (tl + tr) / 2;
return get1(v + v,tl,tm,l,r) + get1(v + v + 1,tm + 1,tr,l,r);
}
/*
8
3 2 3 1 3 3 2 3
*/
vector <int> Ask(int x) {
if(u[x])return was[x];
u[x] = 1;
kol++;
assert(kol <= 10000);
was[x] = ask(x);
return was[x];
}
int find_best(int pp) {
k = pp;
int m = (k - 1) / 2;
for(int i = 0;i < min(k,453);i++) {
kol++;
vector <int> res = Ask(i);
if(res[0] + res[1] == 0)return i;
mx = max(mx,res[0] + res[1]);
}
build(1,0,k - 1);
while(1) {
int l = 0,r = k - 1 - (int)q.size();
while(l <= r) {
int mid = (l + r) / 2;
int zap = get(1,0,k - 1,mid + 1);
vector <int> res = Ask(zap);
int sum = res[0] + res[1];
if(sum == 0)return zap;
if(sum != mx) {
q.pb(mp(zap,sum));
upd(1,0,k - 1,zap);
break;
}
res[0] -= get1(1,0,k - 1,0,zap - 1);
if(res[0] != 0) {
r = mid - 1;
}else {
l = mid + 1;
}
}
}
}