Submission #228053

#	Time	Username	Problem	Language	Result	Execution time	Memory
228053		AaronNaidu	The Big Prize (IOI17_prize)	C++14	0 / 100	68 ms	416 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int n, threshold, fir, sec, counter, globalMin;
int finalReturn = -1;
bool checked[300000];
int firr[300000];
vector<pair<int, int> > regions;



bool isLolly(int x) {
    vector<int> v = ask(x);
    checked[x] = true;
    if (v[0] + v[1] == 0)
    {
        finalReturn = x;
        return true;
    }
    if (v[0] + v[1] > n/2)
    {
        fir = v[0];
        firr[x] = fir;
        sec = v[1];
        return true;
    }
    return false;
}

int stage2(int firstPos, int lastPos, int bigsBeforeFirst, int bigsBeforeLast) {
    //cout << "In stage 2 from " << firstPos << " to " << lastPos << "\n";
    int p = firstPos;
    while (p + 10 < lastPos)
    {
        while (!checked[p] and !isLolly(p))
        {
            p++;
        }
        if (firr[p] > bigsBeforeFirst)
        {
            for (int i = firstPos; i <= p; i++)
            {
                if (!checked[i])
                {
                    isLolly(i);
                }
            }
            bigsBeforeFirst = firr[p];
            firstPos = p;
        }
        p += 10;
    }
    for (int i = p; i <= lastPos; i++)
    {
        if (!checked[i])
        {
            isLolly(i);
        }
    }
    return finalReturn;
}


int find_best(int ln) {
    n = ln;
    if (n <= 5000)
    {
        for (int i = 0; i < n; i++)
        {
            vector<int> v = ask(i);
            if (v[0] == 0 and v[1] == 0)
            {
                return i;
            }   
        }
    }
    fir = 1;
    sec = 1;
    counter = 0;
    /*while (fir + sec < n/2)
    {
       vector<int> v = ask(counter);
        fir = v[0];
        sec = v[1];
        if (fir + sec == 0)
        {
            return counter;
        }
        counter++;
    }
    threshold = fir + sec;
    globalMin = counter; */
    int prevFirsts = 0;
    int prevMin = 0;
    while (counter + 50 < n)
    {
       while (!isLolly(counter))
       {
           counter++;
       }
       if (finalReturn > 0)
       {
           return finalReturn;
       }
       if (firr[counter] > prevFirsts)
       {
           int x = stage2(prevMin, prevMin + 50, prevFirsts, firr[counter]);
           if (x >= 0) {
               return x;
           }
       }
       prevFirsts = firr[counter];
       prevMin = counter;
       counter += 50;
    }
    for (int i = counter; i < n; i++)
    {
        vector<int> v = ask(i);
        checked[i] = true;
        if (v[0] + v[1] == 0)
        {
            return i;
        }
    }
    return finalReturn;
}

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