Submission #73431

#	Time	Username	Problem	Language	Result	Execution time	Memory
73431		Sa1378	The Big Prize (IOI17_prize)	C++17	100 / 100	176 ms	3944 KiB

prize

    #include "prize.h"
    #include <bits/stdc++.h>
    using namespace std;
    #define N ((int)201*1000)
     
    int n,arr[N],lft[N],rght[N];
    int cnt_rght[N],cnt_lft[N];
    bool mark[N];
     
    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);
    }
     
    void add(int x)
    {
    	mark[x]=1;
    	for(int i=x+1;i<n;i++)cnt_lft[i]++;
    	for(int i=x-1;i>=0;i--)cnt_rght[i]++;
    	return ;
    }
     
     
    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<600 && q.size();i++)
    	{
			int l=q.front().first,r=q.front().second;q.pop();
			if(l>=r-1)continue;
			int mid=(l+r)/2;
    		if(query(mid))return mid;
    		if(now<lft[mid]+rght[mid])
    			now=lft[mid]+rght[mid],id=mid;
			q.push({l,mid});
			q.push({mid,r});
    	}
		while(q.size())q.pop();
    	q.push({-1,n});
    	for(int i=0;i<600 && q.size();i++)
    	{
			int l=q.front().first,r=q.front().second;q.pop();
			if(l>=r-1)continue;
			int mid=(l+r)/2;
    		if(now>lft[mid]+rght[mid])
    			add(mid);
			q.push({l,mid});
			q.push({mid,r});
		}
		while(1)
    	{
    		int l=-1,r=n;
    		while(l<r-1)
    		{
    			int mid=(l+r)/2;
    			for(int i=0;;i++)
    			{
    				if(mid+i<r && !mark[mid+i])
    				{
    					mid=mid+i;
    					break;
    				}
    				if(mid-i>l && !mark[mid-i])
    				{
    					mid=mid-i;
    					break;
    				}
    			}
    			if(query(mid))return mid;
    			if(lft[mid]+rght[mid]<now)
    			{
    				add(mid);
    				break;
    			}
    			if((rght[mid]-cnt_rght[mid])-(rght[r]-cnt_rght[r])>0)l=mid;
    			else r=mid;
    		}
    	}
    	
    }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:39:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
       if(now<lft[mid]+rght[mid])
       ^~
prize.cpp:41:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    q.push({l,mid});
    ^
prize.cpp:51:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
       if(now>lft[mid]+rght[mid])
       ^~
prize.cpp:53:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    q.push({l,mid});
    ^
prize.cpp:30:16: warning: variable 'id' set but not used [-Wunused-but-set-variable]
      int now=0,id;
                ^~

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