Submission #52405

#	Time	Username	Problem	Language	Result	Execution time	Memory
52405		Kubalionzzale	The Big Prize (IOI17_prize)	C++14	90 / 100	57 ms	948 KiB

prize

#include "prize.h"

#include <algorithm>
#include <set>
#include <map>

std::map<int, int> mapa;
//first - sum
//second - left

int find_best(int n) {

    if (n <= 500)
    {
        std::vector<int> get;
        for (int i = 0; i < n; ++i)
        {
            get = ask(i);

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


    int max = 0;
    std::vector<int> get;
    std::map<int, std::pair<int, int> > askedBig;
    for (int i = 0; i < 500; ++i)
    {
        get = ask(i);
        if (get[0] + get[1] > max)
        {
            max = get[0] + get[1];
        }
        if (get[0] == 0 && get[1] == 0)
        {
            return i;
        }

        int sum = get[0] + get[1];
        if (mapa.find(sum) == mapa.end())
        {
            mapa.insert(std::make_pair(sum, 0));
        }
        else
        {
            mapa[sum] = get[0];
        }
    }

    int cur = 499;
    while (1)
    {

        if (askedBig.find(cur) != askedBig.end())
        {
            get[0] = askedBig[cur].first;
            get[1] = askedBig[cur].second;
        }
        else
        {
            get = ask(cur);
            askedBig.insert(std::make_pair(cur, std::make_pair(get[0], get[1])));
        }

        if (get[0] == 0 && get[1] == 0)
        {
            return cur;
        }


        while (1 && get[0] + get[1] != max)
        {
            if (askedBig.find(cur + 1) != askedBig.end())
            {
                get[0] = askedBig[cur + 1].first;
                get[1] = askedBig[cur + 1].second;
            }
            else
            {
                get = ask(cur + 1);
                askedBig.insert(std::make_pair(cur + 1, std::make_pair(get[0], get[1])));
            }

            int inner = get[0] + get[1];
            if (inner == 0)
            {
                return cur + 1;
            }
            else if (inner != max)
            {
                mapa[inner] = get[0];
                ++cur;
            }
            else
            {
                mapa[inner] = get[0];
                break;
            }
        }


        bool flag = false;
        for (int i = 8; i >= 0; --i)
        {
            int nr = 1 << i;
            int toAsk = std::min(cur + nr, n - 1);

            if (askedBig.find(toAsk) != askedBig.end())
            {
                get[0] = askedBig[toAsk].first;
                get[1] = askedBig[toAsk].second;
            }
            else
            {
                get = ask(toAsk);
                askedBig.insert(std::make_pair(toAsk, std::make_pair(get[0], get[1])));
            }


            int sum = get[0] + get[1];

            if (get[0] == 0 && get[1] == 0)
            {
                return toAsk;
            }

            if (get[0] == 0 && sum != max)
            {
                mapa.insert(std::make_pair(sum, 0));

                cur = toAsk;
                flag = true;
                break;
            }
            else if (mapa.find(sum) == mapa.end())
            {
                continue;
            }
            else if (get[0] > mapa[sum])
            {
                continue;
            }
            else if (get[0] == mapa[sum] && sum != max)
            {
                cur = toAsk;
                flag = true;
                break;
            }
            else
            {
                cur = toAsk;
            }
        }

        if (!flag)
            ++cur;
    }
}

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