Submission #1203906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203906		nikolashami	The Big Prize (IOI17_prize)	C++20	90 / 100	26 ms	6704 KiB

prize

#include<bits/stdc++.h>
using namespace std;
using ll=int;

#include"prize.h"
const ll L=475/*1*/,N=2e5+2;

map<ll,ll>C;
map<array<ll,2>,array<ll,2>>mp;
ll x,lik,br,l,r,n,qu;

/*ll GG[N];
vector<int>ask(ll x){
	ll le=0,ri=0;
	for(int i=0;i<x;++i)if(GG[i]<GG[x])++le;
	for(int i=x+1;i<n;++i)if(GG[i]<GG[x])++ri;
	return{le,ri};
}*/

struct node{
    ll lz=-1,s=0;
}st[4*N];

void push(int i,int l,int r){
    if(st[i].lz!=-1){
        int m=(l+r)/2;
        st[2*i].s=st[i].lz*(m-l+1),st[2*i+1].s=st[i].lz*(r-m);
        st[2*i].lz=st[2*i+1].lz=st[i].lz;
        st[i].lz=-1;
    }
}

void upd(int l,int r,int x,int i=1,int l2=0,int r2=n-1){
    if(l<=l2&&r2<=r){
        st[i].s=x*(r2-l2+1),st[i].lz=x;
        return;
    }
    push(i,l2,r2);
    int m2=(l2+r2)/2;
    if(l<=m2)upd(l,r,x,2*i,l2,m2);
    if(m2+1<=r)upd(l,r,x,2*i+1,m2+1,r2);
    st[i].s=st[2*i].s+st[2*i+1].s;
}

int get(int l,int r,int i=1,int l2=0,int r2=n-1){
    if(l<=l2&&r2<=r)return st[i].s;
    push(i,l2,r2);
    int m2=(l2+r2)/2,S=0;
    if(l<=m2)S+=get(l,r,2*i,l2,m2);
    if(m2+1<=r)S+=get(l,r,2*i+1,m2+1,r2);
    return S;
}

mt19937_64 rng(time(0));

vector<int>askk(int aa){
	//cout<<"A"<<endl;
	ll G=get(aa,aa);
	//cout<<G<<endl;
	if(G){
		G-=L;
		if(mp.find({G-x})==mp.end()){
			mp[{G,x-G}][0]=max(mp[{G,x-G}][0],aa);
			mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
		}
		mp[{G,x-G}][0]=min(mp[{G,x-G}][0],aa);
		mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
		upd(mp[{G,x-G}][0],mp[{G,x-G}][1],G+L);
		//cout<<"1: ";
		//cout<<aa<<' '<<G<<' '<<x-G<<endl;
		return{G,x-G};
	}
	vector<int>a=ask(aa);
	++qu;
	if(a[0]+a[1]!=x){
		//cout<<"2: ";
		//cout<<aa<<' '<<a[0]<<' '<<a[1]<<endl;
		return a;
	}
	G=a[0];
	if(mp.find({G-x})==mp.end()){
		mp[{G,x-G}][0]=max(mp[{G,x-G}][0],aa);
		mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
	}
	mp[{G,x-G}][0]=min(mp[{G,x-G}][0],aa);
	mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
	upd(mp[{G,x-G}][0],mp[{G,x-G}][1],G+L);
	//cout<<"3: ";
	//cout<<aa<<' '<<G<<' '<<x-G<<endl;
	return{G,x-G};
}

int find_best(int NN){
	n=NN;
	for(int i=0;i<=4*NN;++i)
		st[i]={-1,0};
	mp.clear();
	C.clear();
	for(int i=0;i<L;++i){ //<L
		vector<int>a=ask(i);
		++C[a[0]+a[1]];
		if(!a[0]&&!a[1])return i;
	}
	x=0,lik=L-1;
	for(auto[u,v]:C)x=max(x,u);
	br=L-C[x];
	qu=0;
	ll LL;
	float BL;
	LL=rng();
	LL=abs(LL);
	BL=LL;
	while(BL>1)BL/=10;
	for(int R=0;R<n;R+=L/(3.5+BL)){
		vector<int>a=askk(R);
		if(!a[0]&&!a[1])return R;
		LL=rng();
		LL=abs(LL);
		BL=LL;
		while(BL>1)BL/=10;
	}
	while(lik<n){
		l=lik+1,r=n-1;
		while(l<=r){
			ll m=(l+r)/2;
			vector<int>a=askk(m);
			if(!a[0]&&!a[1])return m;
			else if(a[0]+a[1]==x){
				if(a[0]!=br)r=m-1;
				else l=m+1;
			}else{
				lik=m;
				r=m-1;
			}
		}
		++br;
		//assert(0);
	}
	return -1;
}

/*signed main(){
	ll NN;cin>>NN;
	for(int i=0;i<NN;++i)
		cin>>GG[i];
	cout<<find_best(NN);
}*/

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