Submission #527392

#	Time	Username	Problem	Language	Result	Execution time	Memory
527392		andreiomd	The Big Prize (IOI17_prize)	C++11	0 / 100	109 ms	200 KiB

prize

#include "prize.h"

using namespace std;

const int NMAX = 2e5 + 10;

typedef pair < int, int > PII;

int mars[NMAX];

int find_best (int n)
{
    vector < PII > Seg;

    for(int i = 0; i < n; ++i)
    {
        int left = i, right = n - 1, pos = -1;

        vector < int > now = ask(i);
        if(now[0] == 0 && now[1] == 0)
            return i;

        if(now[0] == i && now[1] == (n - i - 1))
        {
            while(left <= right)
            {
                int mid = ((left + right) >> 1);
                vector < int > _temp = ask(mid);

                if(_temp[0] == now[0])
                    left = mid + 1, pos = mid;
                else right = mid - 1;
            }

            Seg.push_back({i, pos});

            i = pos;
        }
    }

    for(auto it : Seg)
        ++mars[it.first], --mars[it.second + 1];

    for(int i = 1; i < n; ++i)
        mars[i] += mars[i - 1];

    for(int i = 0; i < n; ++i)
        if(mars[i] == 0)
    {
        vector < int > now = ask(i);

        if(now[0] == 0 && now[1] == 0)
            return i;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:13:20: warning: control reaches end of non-void function [-Wreturn-type]
   13 |     vector < PII > Seg;
      |                    ^~~

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