답안 #52404 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52404	2018-06-25T21:44:43 Z	Kubalionzzale	커다란 상품 (IOI17_prize)	C++14	90 / 100	110 ms	1100 KB

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)
        {
            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 = 18; 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.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	292 KB	Output is correct
2	Correct	6 ms	436 KB	Output is correct
3	Correct	5 ms	436 KB	Output is correct
4	Correct	5 ms	564 KB	Output is correct
5	Correct	5 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	8 ms	564 KB	Output is correct
8	Correct	3 ms	564 KB	Output is correct
9	Correct	8 ms	564 KB	Output is correct
10	Correct	5 ms	564 KB	Output is correct

Subtask #2
70.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	564 KB	Output is correct
2	Correct	3 ms	564 KB	Output is correct
3	Correct	4 ms	564 KB	Output is correct
4	Correct	4 ms	564 KB	Output is correct
5	Correct	6 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	5 ms	564 KB	Output is correct
8	Correct	5 ms	564 KB	Output is correct
9	Correct	5 ms	564 KB	Output is correct
10	Correct	5 ms	564 KB	Output is correct
11	Correct	4 ms	568 KB	Output is correct
12	Correct	6 ms	568 KB	Output is correct
13	Correct	8 ms	568 KB	Output is correct
14	Correct	7 ms	572 KB	Output is correct
15	Correct	14 ms	572 KB	Output is correct
16	Partially correct	52 ms	956 KB	Partially correct - number of queries: 7433
17	Correct	4 ms	956 KB	Output is correct
18	Partially correct	65 ms	960 KB	Partially correct - number of queries: 8641
19	Correct	6 ms	960 KB	Output is correct
20	Correct	15 ms	960 KB	Output is correct
21	Correct	26 ms	960 KB	Output is correct
22	Correct	12 ms	960 KB	Output is correct
23	Correct	8 ms	960 KB	Output is correct
24	Correct	7 ms	960 KB	Output is correct
25	Correct	41 ms	960 KB	Output is correct
26	Correct	36 ms	960 KB	Output is correct
27	Correct	9 ms	960 KB	Output is correct
28	Partially correct	71 ms	960 KB	Partially correct - number of queries: 8058
29	Partially correct	45 ms	960 KB	Partially correct - number of queries: 6208
30	Partially correct	72 ms	1084 KB	Partially correct - number of queries: 8582
31	Correct	3 ms	1084 KB	Output is correct
32	Correct	10 ms	1084 KB	Output is correct
33	Correct	2 ms	1084 KB	Output is correct
34	Correct	33 ms	1084 KB	Output is correct
35	Correct	9 ms	1084 KB	Output is correct
36	Correct	29 ms	1084 KB	Output is correct
37	Correct	10 ms	1084 KB	Output is correct
38	Correct	3 ms	1084 KB	Output is correct
39	Correct	33 ms	1084 KB	Output is correct
40	Partially correct	66 ms	1084 KB	Partially correct - number of queries: 7248
41	Partially correct	45 ms	1084 KB	Partially correct - number of queries: 5221
42	Partially correct	39 ms	1084 KB	Partially correct - number of queries: 5221
43	Correct	35 ms	1084 KB	Output is correct
44	Correct	31 ms	1084 KB	Output is correct
45	Correct	30 ms	1084 KB	Output is correct
46	Correct	6 ms	1084 KB	Output is correct
47	Correct	25 ms	1084 KB	Output is correct
48	Partially correct	27 ms	1084 KB	Partially correct - number of queries: 6536
49	Correct	12 ms	1084 KB	Output is correct
50	Partially correct	77 ms	1084 KB	Partially correct - number of queries: 8568
51	Correct	33 ms	1084 KB	Output is correct
52	Correct	6 ms	1084 KB	Output is correct
53	Correct	5 ms	1084 KB	Output is correct
54	Correct	35 ms	1084 KB	Output is correct
55	Correct	5 ms	1084 KB	Output is correct
56	Partially correct	63 ms	1084 KB	Partially correct - number of queries: 8640
57	Partially correct	67 ms	1084 KB	Partially correct - number of queries: 6396
58	Partially correct	56 ms	1084 KB	Partially correct - number of queries: 6483
59	Partially correct	42 ms	1084 KB	Partially correct - number of queries: 5221
60	Correct	44 ms	1084 KB	Output is correct
61	Correct	7 ms	1084 KB	Output is correct
62	Correct	7 ms	1084 KB	Output is correct
63	Correct	5 ms	1084 KB	Output is correct
64	Correct	6 ms	1084 KB	Output is correct
65	Correct	6 ms	1084 KB	Output is correct
66	Correct	7 ms	1084 KB	Output is correct
67	Correct	5 ms	1084 KB	Output is correct
68	Correct	4 ms	1084 KB	Output is correct
69	Correct	8 ms	1084 KB	Output is correct
70	Correct	6 ms	1084 KB	Output is correct
71	Partially correct	71 ms	1084 KB	Partially correct - number of queries: 8379
72	Correct	10 ms	1084 KB	Output is correct
73	Partially correct	78 ms	1084 KB	Partially correct - number of queries: 8270
74	Partially correct	81 ms	1084 KB	Partially correct - number of queries: 8308
75	Correct	6 ms	1084 KB	Output is correct
76	Partially correct	57 ms	1084 KB	Partially correct - number of queries: 7180
77	Partially correct	110 ms	1084 KB	Partially correct - number of queries: 8492
78	Correct	6 ms	1084 KB	Output is correct
79	Correct	32 ms	1084 KB	Output is correct
80	Partially correct	72 ms	1084 KB	Partially correct - number of queries: 8516
81	Partially correct	92 ms	1100 KB	Partially correct - number of queries: 8494
82	Partially correct	73 ms	1100 KB	Partially correct - number of queries: 8346
83	Correct	7 ms	1100 KB	Output is correct
84	Partially correct	64 ms	1100 KB	Partially correct - number of queries: 7042
85	Partially correct	94 ms	1100 KB	Partially correct - number of queries: 8535
86	Correct	8 ms	1100 KB	Output is correct
87	Correct	8 ms	1100 KB	Output is correct
88	Correct	4 ms	1100 KB	Output is correct
89	Correct	7 ms	1100 KB	Output is correct
90	Correct	6 ms	1100 KB	Output is correct
91	Correct	6 ms	1100 KB	Output is correct
92	Correct	7 ms	1100 KB	Output is correct
93	Correct	7 ms	1100 KB	Output is correct
94	Correct	8 ms	1100 KB	Output is correct
95	Correct	8 ms	1100 KB	Output is correct
96	Correct	10 ms	1100 KB	Output is correct
97	Correct	7 ms	1100 KB	Output is correct

답안 #52404

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 70.0 / 80.0

Subtask #1
20.0 / 20.0

Subtask #2
70.0 / 80.0