Submission #38415

#	Time	Username	Problem	Language	Result	Execution time	Memory
38415		MatheusLealV	The Big Prize (IOI17_prize)	C++14	90 / 100	99 ms	2796 KiB

prize

#include <bits/stdc++.h>
#define N 200050
#define d min(i + 500, n)
#include "prize.h"
using namespace std;

int n, v[N];

int find_best(int n)
{
    int sum = 0, p = 500;

    for(int i = 0; i < min(n, 500); i++)
    {
        vector<int> aux = ask(i);

        sum = max(sum, aux[0] + aux[1]);

        if(aux[0] + aux[1] == 0) return i;
    }

    while(p < n)
    {
        vector<int> aux = ask(p);

        if(aux[0] + aux[1] == 0) return p;

        int ini = p + 1, fim = n - 1, mid;

        if(aux[0] + aux[1] == sum)
        {
            while(fim >= ini)
            {
                mid = (ini + fim)/2;

                vector<int> atual = ask(mid);

                if(atual[0] + atual[1] == 0) return mid;

                if(ini == fim) break;

                if(atual[0] + atual[1] < sum) fim = mid;
                else
                {
                    if(aux[1] - atual[1] > 0) fim = mid - 1;
                    else ini = mid + 1;
                }
            }

            p = ini + 1;

        } else p++;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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