Submission #63606

#	Time	Username	Problem	Language	Result	Execution time	Memory
63606		MKopchev	The Big Prize (IOI17_prize)	C++14	100 / 100	57 ms	580 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int test(vector<int> q)
{
    if(q[0]==0&&q[1]==0)return 1;
    return 0;
}
vector<int> arr;
int ans;
void solve(int l,vector<int> arr_l,int r,vector<int> arr_r)
{
    if(r-l<=1)return;
    if(arr_l==arr_r)return;
    if(ans!=-1)return;
    int av=(l+r)/2;
    vector<int> arr_av=ask(av);
    if(test(arr_av))
    {
        ans=av;
        return;
    }
    if(arr_l[0]+arr_l[1]==arr_r[0]+arr_r[1])
    {
        if(arr_av[0]+arr_av[1]<arr_l[0]+arr_l[1]&&arr_l[0]==arr_r[0]-1)return;
    }
    if(rand()%2)
    {
    solve(l,arr_l,av,arr_av);
    solve(av,arr_av,r,arr_r);
    }
    else
    {
    solve(av,arr_av,r,arr_r);
    solve(l,arr_l,av,arr_av);
    }
}
int find_best(int n)
{
    srand(time(0));
    vector<int> l=ask(0);
    if(test(l))return 0;
    vector<int> r=ask(n-1);
    if(test(r))return n-1;
    ans=-1;
    solve(0,l,n-1,r);
    return ans;
}

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