Submission #1238544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238544		vivkostov	The Big Prize (IOI17_prize)	C++20	97.63 / 100	13 ms	1196 KiB

prize

//#pragma once
//#include "grader.cpp"
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 mt(time(nullptr));
int sum,lamp,nn,num=10,lf,rf,rr,used[200005];
void prec()
{
    vector<int>a;
    int h;
    for(int i=1; i<=500; i++)
    {
        //h=((i*199942+7424)/3)%nn;
        h=mt()%nn;
        a=ask(h);
        sum=max(sum,a[0]+a[1]);
        a.clear();
    }
    /*if(nn>=105689)
    {
        h=105687;
        a=ask(h);
        sum=max(sum,a[0]+a[1]);
        h--;
        a=ask(h);
        sum=max(sum,a[0]+a[1]);
        h+=2;
        a=ask(h);
        sum=max(sum,a[0]+a[1]);
    }*/
}
void rec(int l,int r,int br,int exl,int exr,int dul)
{
    if(lamp)return;
    int mid=(l+r)/2,ad=1;
    vector<int>a;
    while(true)
    {
        if(num>=9998)
        {
            lamp=sum+20000000;
            return;
        }
        used[mid-1]=1;
        a.clear();
        a=ask(mid-1);
        num++;
        if(a[0]+a[1]==0)
        {
            lamp=mid;
            return;
        }
        if(a[0]==0)lf=mid+1;
        if(a[1]==0)rf=mid-1;
        if(a[0]+a[1]==sum)
        {
            break;
        }
        else rr=mid-1;
        mid+=ad;
        if(mid>r)
        {
            mid=(l+r)/2-1;
            ad=-1;
        }
        if(mid<l)return;
    }
    int dist=abs(mid-(l+r)/2);
    if(mid>=(l+r)/2)
    {
        //if(a[1]-exr>0&&a[0]-exl-dist>0)rr++;
        if(a[1]-exr>0)rec(mid+1,r,a[1]-exr,a[0],exr,dul+1);
        if(a[0]-exl-dist>0)rec(l,(l+r)/2-1,a[0]-exl-dist,exl,a[1]+dist,dul+1);
    }
    else
    {
        if(a[0]-exl>0)rec(l,mid-1,a[0]-exl,exl,a[1],dul+1);
    }
}
int find_best(int N)
{
    nn=N;
    rf=N;
    prec();
    rec(1,nn,sum,0,0,1);
    return lamp-1;
}

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