oj.uz

Submission #52381

# Submission time Handle Problem Language Result Execution time Memory
52381 2018-06-25T17:12:01 Z Kubalionzzale The Big Prize (IOI17_prize) C++14
20 / 100
 92 ms 1044 KB 
#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;
    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;
    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);
                    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);
                            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);
                            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

prize.cpp: In function 'int find_best(int)':
prize.cpp:57:13: warning: unused variable 'toLeft' [-Wunused-variable]
         int toLeft = mapa[max];
             ^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Output is correct
2 Correct 4 ms 380 KB Output is correct
3 Correct 7 ms 412 KB Output is correct
4 Correct 9 ms 412 KB Output is correct
5 Correct 7 ms 412 KB Output is correct
6 Correct 2 ms 412 KB Output is correct
7 Correct 7 ms 484 KB Output is correct
8 Correct 7 ms 504 KB Output is correct
9 Correct 5 ms 516 KB Output is correct
10 Correct 8 ms 528 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 528 KB Output is correct
2 Correct 6 ms 528 KB Output is correct
3 Correct 7 ms 528 KB Output is correct
4 Correct 6 ms 528 KB Output is correct
5 Correct 7 ms 528 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 9 ms 560 KB Output is correct
8 Correct 5 ms 560 KB Output is correct
9 Correct 7 ms 560 KB Output is correct
10 Correct 6 ms 572 KB Output is correct
11 Incorrect 92 ms 1044 KB Incorrect
12 Halted 0 ms 0 KB -