제출 #520405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520405		AdamGS	커다란 상품 (IOI17_prize)	C++17	20 / 100	3024 ms	1880 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int tr[4*LIM], ile, N=1;
int T[LIM][2], wynik=-1;
void pytaj(int x) {
	if(T[x][0]!=-1) return;
	vector<int>V=ask(x);
	T[x][0]=V[0];
	T[x][1]=V[1];
	if(T[x][0]+T[x][1]==0) wynik=x;
}
void upd(int v) {
	v+=N;
	tr[v]=1;
	v/=2;
	while(v) {
		tr[v]=tr[2*v]+tr[2*v+1];
		v/=2;
	}
}
int cnt(int l, int r) {
	if(r<l) return 0;
	l+=N; r+=N;
	int ans=tr[l];
	if(l!=r) ans+=tr[r];
	while(l/2!=r/2) {
		if(l%2==0) ans+=tr[l+1];
		if(r%2==1) ans+=tr[r-1];
		l/=2; r/=2;
	}
	return ans;
}
void solve(int l, int r) {
	int mid=(l+r)/2;
	pytaj(mid);
	if(wynik!=-1) return;
	while(T[mid][0]+T[mid][1]<ile && mid<r) {
		upd(mid);
		++mid;
		pytaj(mid);
		if(wynik!=-1) return;
	}
	if(T[mid][0]+T[mid][1]<ile) {
		upd(mid);
		mid=(l+r)/2;
		pytaj(mid);
		if(wynik!=-1) return;
		while(T[mid][0]+T[mid][1]<ile && mid>l) {
			upd(mid);
			--mid;
			pytaj(mid);
			if(wynik!=-1) return;
		}
		if(T[mid][0]+T[mid][1]<ile) return;
	}
	if(cnt(0, mid-1)<T[mid][0]) solve(l, mid-1);
	if(wynik!=-1) return;
	if(cnt(mid+1, N-1)<T[mid][1]) solve(mid+1, r);
}
int find_best(int n) {
	rep(i, n) T[i][0]=-1;
	while(N<n) N*=2;
	rep(i, min(n, 500)) {
		pytaj(i);
		ile=max(ile, T[i][0]+T[i][1]);
		if(wynik!=-1) return i;
	}
	solve(0, n-1);
	return wynik;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80