Submission #1230608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230608		LeonidCuk	The Big Prize (IOI17_prize)	C++17	97.60 / 100	22 ms	11364 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int res=-1;
bool check=false;
vector<vector<int>>v;
void dvq(int l,int r)
{
    if(check)return;
    if(r-l<2)return;
    int m=(l+r)/2;
    auto temp=ask(m);
    v[m][0]=temp[0];
    v[m][1]=temp[1];
    if(v[m][0]+v[m][1]==0)
    {
        res=m;
        check=true;
        return;
    }
    if(v[m][0]+v[m][1]==v[l][1]+v[l][0])
    {
        if(v[m][0]-v[l][0]!=0)dvq(l,m);
    }
    else if(v[m][0]!=0)dvq(l,m);
    if(v[m][0]+v[m][1]==v[r][1]+v[r][0])
    {
        if(v[m][1]-v[r][1]!=0)dvq(m,r);
    }
    else if(v[m][1]!=0)dvq(m,r);
}
int find_best(int n)
{
    v.resize(n);
    for(int i=0;i<n;i++)
    {
        v[i].resize(2);
    }
    auto temp=ask(0);
    v[0][0]=temp[0];
    v[0][1]=temp[1];
    if(v[0][0]+v[0][1]==0)return 0;
    temp=ask(n-1);
    v[n-1][0]=temp[0];
    v[n-1][1]=temp[1];
    if(v[n-1][0]+v[n-1][1]==0)return n-1;
    dvq(0,n-1);
    return res;
}

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