제출 #520615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520615		AdamGS	The Big Prize (IOI17_prize)	C++17	0 / 100	6 ms	1868 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 v) {
	v+=N;
	int ans=tr[v];
	while(v>1) {
		if(v%2==1) ans+=tr[v-1];
		v/=2;
	}
	return ans;
}
void pytaj2(int x) {
	pytaj(x);
	if(T[x][0]+T[x][1]<ile) upd(x);
}
void solve(int l, int r, int k) {
	if(l>r) return;
	if(cnt(r)==k) return;
	if(l==r) {
		pytaj2(l);
		return;
	}
	int mid=(l+r)/2;
	pytaj2(mid);
	while(T[mid][0]+T[mid][1]<ile && mid<r) {
		++mid;
		pytaj2(mid);
	}
	if(T[mid][0]+T[mid][1]==ile) {
		solve(l, mid-1, T[mid][0]);
		solve(mid+1, r, k);
	} else {
		mid=(l+r)/2;
		while(T[mid][0]+T[mid][1]<ile && mid>l) {
			--mid;
			pytaj2(mid);
		}
		if(T[mid][0]+T[mid][1]==ile) {
			solve(l, mid-1, T[mid][0]);
		}
	}
}
int find_best(int n) {
	rep(i, n) T[i][0]=-1;
	if(n<=5000) {
		rep(i, n) pytaj(i);
		return wynik;
	}
	while(N<n) N*=2;
	int p=n/450;
	for(int i=p; i<n; i+=p) {
		pytaj(i);
		ile=max(ile, T[i][0]+T[i][1]);
	}
	rep(i, n) if(T[i][0]!=-1) pytaj2(i);
	int x=p;
	while(T[x][0]+T[x][1]<ile && x>0) {
		--x;
		pytaj2(x);
	}
	if(T[x][0]+T[x][1]<ile) upd(x);
	if(x>0) solve(0, x-1, T[x][0]);
	for(int i=p; i+p<n; i+=p) {
		x=i;
		while(T[x][0]+T[x][1]<ile && x<i+p) {
			++x;
			pytaj2(x);
		}
		int y=min(i+p, n-1);
		pytaj2(y);
		while(T[y][0]+T[y][1]<ile && y>x) {
			--y;
			pytaj2(y);
		}
		if(x+1<=y-1) solve(x+1, y-1, T[y][0]);
	}
	return wynik;
}

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