Submission #1248128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248128		denislav	The Big Prize (IOI17_prize)	C++20	90 / 100	24 ms	956 KiB

prize

# include <iostream>
# include <vector>
# include <cassert>
# include <map>
using namespace std;
# include "prize.h"
//# include "grader.cpp"

int n;
map<int,pair<int,int>> Data;

pair<int,int> query(int i)
{
    if(Data.find(i)==Data.end())
    {
        vector<int> arr=ask(i);
        Data[i]={arr[0],arr[1]};
    }

    return Data[i];
}

int s,big;

bool large(int i)
{
    pair<int,int> pa=query(i);
    long long sum=pa.first+pa.second;
    return sum==big;
}

void rec(int l, int r)
{
    //cout<<l<<" "<<r<<"\n";
    if(l==r) return ;

    pair<int,int> L=query(l),R=query(r);
    if(L.second==R.second or L.first==R.first) return ;

    int mid=(l+r)/2;
    for(int i=mid;i>=l;i--)
    {
        if(large(i))
        {
            rec(l,i);
            break;
        }
    }

    for(int i=mid+1;i<=r;i++)
    {
        if(large(i))
        {
            rec(i,r);
            break;
        }
    }
}

int find_best(int N)
{
    n=N;

    for(long long i=1;i<=n;i++)
    {
        if(i*i>=n)
        {
            s=i;
            break;
        }
    }

    s*=2;
    for(int i=0;i<min(s,n);i++)
    {
        pair<int,int> pa=query(i);
        int sum=pa.first+pa.second;
        if(big<sum) big=sum;
    }

    int l=n-1,r=0;
    for(int i=0;i<n;i++)
    {
        if(large(i))
        {
            l=i;
            break;
        }
    }

    for(int i=n-1;i>=0;i--)
    {
        if(large(i))
        {
            r=i;
            break;
        }
    }

    rec(l,r);

    for(auto P: Data)
    {
        int id=P.first;
        int sum=P.second.first+P.second.second;
        if(sum==0) return id;
    }

    assert(0);
    return -1;
}

/*
8
3 2 3 1 3 3 2 3
*/

/*
8
2 1 2 2 2 2 2 2 2
*/

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