Submission #52385

#	Time	Username	Problem	Language	Result	Execution time	Memory
52385		Kubalionzzale	The Big Prize (IOI17_prize)	C++14	20 / 100	1063 ms	1096 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) {


    int q = 0;

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

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


    int max = 0;
    std::vector<int> get;
    for (int i = 0; i < 500; ++i)
    {
        get = ask(i);
        ++q;
        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;
    std::map<int, std::pair<int, int> > askedBig;
    while (1)
    {
        int toLeft = mapa[max];

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

            if (asked.find(toAsk) == asked.end())
            {
                if (askedBig.find(toAsk) != askedBig.end())
                {
                    get[0] = askedBig[toAsk].first;
                    get[1] = askedBig[toAsk].second;
                }
                else
                {
                    get = ask(toAsk);
                    ++q;
                    if (q >= 10000)
                    {
                        while (1)
                        {
                            int x;
                        }
                    }
                    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)
                {
                    mapa.insert(std::make_pair(sum, 0));

                    cur = toAsk;
                    while (1)
                    {
                        if (askedBig.find(cur + 1) != askedBig.end())
                        {
                            get[0] = askedBig[cur + 1].first;
                            get[1] = askedBig[cur + 1].second;
                        }
                        else
                        {
                            get = ask(cur + 1);

                    ++q;
                    if (q >= 10000)
                    {
                        while (1)
                        {
                            int x;
                        }
                    }
                            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;
                        }
                    }

                    flag = true;
                    break;
                }
                else if (get[0] == mapa[sum] && sum != max)
                {
                    cur = toAsk;
                    while (1)
                    {
                        if (askedBig.find(cur + 1) != askedBig.end())
                        {
                            get[0] = askedBig[cur + 1].first;
                            get[1] = askedBig[cur + 1].second;
                        }
                        else
                        {

                            get = ask(cur + 1);

                    ++q;
                    if (q >= 10000)
                    {
                        while (1)
                        {
                            int x;
                        }
                    }
                            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;
                        }
                    }

                    flag = true;
                    break;
                }
                else if (get[0] == mapa[sum])
                {
                    cur = toAsk;
                }
            }
        }

        if (!flag)
            ++cur;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:86:33: warning: unused variable 'x' [-Wunused-variable]
                             int x;
                                 ^
prize.cpp:121:33: warning: unused variable 'x' [-Wunused-variable]
                             int x;
                                 ^
prize.cpp:169:33: warning: unused variable 'x' [-Wunused-variable]
                             int x;
                                 ^
prize.cpp:62:13: warning: unused variable 'toLeft' [-Wunused-variable]
         int toLeft = mapa[max];
             ^~~~~~

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