Submission #827267

#	Time	Username	Problem	Language	Result	Execution time	Memory
827267		vnm06	The Big Prize (IOI17_prize)	C++14	97.41 / 100	52 ms	2096 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"

using namespace std;

bool asked[200005];
int otgv[200005][2];

vector<int> ask2(int pos)
{
    vector<int> anst;
    if(asked[pos]) {anst.push_back(otgv[pos][0]); anst.push_back(otgv[pos][1]); return anst;}
    asked[pos]=1;
    anst=ask(pos);
    otgv[pos][0]=anst[0];
    otgv[pos][1]=anst[1];
    return anst;
}

bool findans=0;
int pos=0, brask=0;
int maxsum=0;

void solve(int le, int ri, int bal_le, int bal_ri, int br)
{
    if(le>ri || !br) return;
    int mid=(le+ri)/2;
    if(ri-le>500) mid+=50;
    vector<int> res=ask2(mid);
    if(res[0] + res[1] == 0)
    {
        findans=1;
        pos=mid;
        return;
    }
    if(res[0]+res[1]==maxsum)
    {
        solve(le, mid-1, bal_le, res[1], res[0]-bal_le);
        if(findans) return;
        solve(mid+1, ri, res[0], bal_ri, res[1]-bal_ri);
        return;
    }
    int m2=mid;
    while(m2-1>=le && res[0]+res[1]!=maxsum)
    {
        m2--;
        res=ask2(m2);
       /// cout<<m2<<endl;
        if(res[0] + res[1] == 0)
        {
            findans=1;
            pos=m2;
            return;
        }
    }
    if(m2==le && res[0]+res[1]<maxsum) solve(mid+1, ri, bal_le+mid-le+1, bal_ri, br-mid+le-1);
    else
    {
        solve(le, m2, bal_le, res[1], res[0]-bal_le);
        if(findans) return;
        solve(mid+1, ri, maxsum-bal_ri-(br-(res[0]-bal_le)-(mid-m2)), bal_ri, br-(res[0]-bal_le)-(mid-m2));

    }
}

int find_best(int n)
{
	for(int i = 0; i<500; i++)
    {
		vector<int> res = ask2(i);
		if(res[0] + res[1] == 0) return i;
        if(res[0]+res[1]>maxsum) maxsum=res[0]+res[1];
	}
	int brl=0;
    for(int i=0; i<500; i++)
    {
		vector<int> res = ask2(i);
        if(res[0]+res[1]<maxsum) brl++;
    }
    solve(500, n-1, brl, 0, maxsum-brl);
	return pos;
}

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