Submission #73425

#	Time	Username	Problem	Language	Result	Execution time	Memory
73425		Sa1378	The Big Prize (IOI17_prize)	C++17	20 / 100	188 ms	12612 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)201*1000)

int n,lft[N],rght[N];
int fen[N];
bool mark[N];

int query2(int x)
{
	x++;
	int res=0;
	for(;x<=n+1;x+=x&-x)res+=fen[x];
	return res;
}

set <int> s;

void add(int x)
{
	mark[x]=1;s.erase(x);
	x++;
	for(;x>0;x-=x&-x)fen[x]++;
}

bool query(int x)
{
	if(lft[x]+rght[x]>0)return 0;
	vector <int> vec;vec=ask(x);
	lft[x]=vec[0];rght[x]=vec[1];
	return (lft[x]+rght[x]==0);
}


int find_best(int n2)
{
	n=n2;
	int now=0,id;
	queue <pair<int,int> > q;
	q.push({-1,n});
	for(int i=0;i<300 && q.size();i++)
	{
		int l=q.front().first,r=q.front().second;q.pop();
		int mid=(l+r)/2;
		if(query(mid))return mid;
		if(now<lft[mid]+rght[mid])
			now=lft[mid]+rght[mid],id=mid;
		if(mid<r-1)q.push({mid,r});
		if(l<mid-1)q.push({l,mid});
	}
	for(int i=0;i<n;i++)s.insert(i);
	while(q.size())q.pop();
	q.push({-1,n});
	for(int i=0;i<300 && q.size();i++)
	{
		int l=q.front().first,r=q.front().second;q.pop();
		int mid=(l+r)/2;
		if(now>lft[mid]+rght[mid])
			add(mid);
		if(mid<r-1)q.push({mid,r});
		if(l<mid-1)q.push({l,mid});
	}
	for(int t=0;t<600;t++)
	{
		int l=-1,r=n;
		while(l<r-1)
		{
			int mid=(l+r)/2;
			auto it=s.lower_bound(mid);
			if(it==s.end() || *it>=r)it--;
			mid=*it;
			if(query(mid))return mid;
			if(lft[mid]+rght[mid]<now)
			{
				add(mid);
				break;
			}
			if((rght[mid]-query2(mid))-(rght[r]-query2(r))>0)l=mid;
			else r=mid;
		}
	}
	
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:39:12: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int now=0,id;
            ^~
prize.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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