Submission #527406

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

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair < int, int > PII;

const int NMAX = 2e5 + 10;

int mars[NMAX];

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

    vector < int > Q;
    for(int i = 0; i < n; ++i)
        Q.push_back(i);
    random_shuffle(Q.begin(), Q.end());

    int Max = 0;
    for(int i = 0; i < 49 && i < n; ++i)
    {
        int pos = Q[i];
        vector < int > _temp = ask(pos);
        if(_temp[0] + _temp[1] > Max)
            Max = _temp[0] + _temp[1];
        if(_temp[0] == 0 && _temp[1] == 0)
            return pos;
    }

    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] + now[1]) == Max)
        {
            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:14:20: warning: control reaches end of non-void function [-Wreturn-type]
   14 |     vector < PII > Seg;
      |                    ^~~

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