답안 #52385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52385 2018-06-25T17:20:53 Z Kubalionzzale 커다란 상품 (IOI17_prize) C++14
20 / 100
1000 ms 1096 KB
#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

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];
             ^~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 7 ms 308 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 5 ms 440 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 9 ms 472 KB Output is correct
8 Correct 6 ms 500 KB Output is correct
9 Correct 6 ms 500 KB Output is correct
10 Correct 6 ms 500 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 500 KB Output is correct
2 Correct 8 ms 684 KB Output is correct
3 Correct 7 ms 684 KB Output is correct
4 Correct 4 ms 684 KB Output is correct
5 Correct 7 ms 684 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 7 ms 684 KB Output is correct
8 Correct 4 ms 684 KB Output is correct
9 Correct 7 ms 684 KB Output is correct
10 Correct 6 ms 684 KB Output is correct
11 Execution timed out 1063 ms 1096 KB Time limit exceeded
12 Halted 0 ms 0 KB -