Submission #708167

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708167	2023-03-11T07:51:16 Z	Cyanmond	The Big Prize (IOI17_prize)	C++17	91.59 / 100	69 ms	2644 KB

prize

#include "prize.h"
#include <bits/stdc++.h>

int lm(int x) {
    std::vector<int> val;
    val = {1};
    while (true) {
        const int a = val.back();
        val.push_back(a * a + 1);
        if (std::accumulate(val.begin(), val.end(), 0) > x) {
            break;
        }
    }
    val.pop_back();
    if (val.size() == 1) {
        return 0;
    }
    while (true) {
        val[val.size() - 2]++;
        val[val.size() - 1] = val[val.size() - 2] * val[val.size() - 2] + 1;
        if (std::accumulate(val.begin(), val.end(), 0) > x) {
            val[val.size() - 2]--;
            return x - val[val.size() - 2] * val[val.size() - 2] - 1;
        }
    }
    return -1;
}

std::map<int, std::vector<int>> askMemo;

std::vector<int> Ask(int i) {
    if (askMemo.find(i) != askMemo.end()) return askMemo[i];
    return askMemo[i] = ask(i);
}

std::vector<int> findLower(std::vector<int> ids) {
    auto question = [&](const int i) {
        return Ask(ids[i]);
    };

    const int n = (int)ids.size();
    const int limit = lm(n);
    std::vector<std::vector<int>> vals;
    for (int i = 0; i <= limit; ++i) {
        vals.push_back(question(i));
    }
    int df = 0;
    for (const auto &vec : vals) {
        df = std::max(df, vec[0] + vec[1]);
    }
    std::vector<int> lws;

    auto relax = [&](int i, std::vector<int> &ans) {
        for (const auto e : lws) {
            if (e < i) --ans[0];
            if (e > i) --ans[1];
        }
    };

    auto solve = [&](auto &&self, const int l, const int r, const int lv, const int rv) -> void {
        const int mid = (l + r) / 2;
        int lm = -1;
        for (int i = mid; i < r; ++i) {
            auto x = question(i);
            if (x[0] + x[1] != df) {
                lws.push_back(ids[i]);
            } else {
                lm = i;
                break;
            }
        }
        int rm = n + 1;
        if (lm == mid) rm = mid;
        else {
            for (int i = mid - 1; i >= l; --i) {
                auto x = question(i);
                if (x[0] + x[1] != df) {
                    lws.push_back(ids[i]);
                } else {
                    rm = i;
                    break;
                }
            }
        }
        if (rm != n + 1) {
            auto x = question(rm);
            // relax(rm, x);
            const int newLv = lv, newRv = x[1];
            if (newLv + newRv != df) {
                self(self, l, rm, newLv, newRv);
            }
        }
        if (lm != -1) {
            auto x = question(lm);
            const int newLv = x[0], newRv = rv;
            if (newLv + newRv != df) {
                self(self, lm + 1, r, newLv, newRv);
            }
        }
    };
    solve(solve, 0, n, 0, 0);
    std::sort(lws.begin(), lws.end());
    return lws;
}

int find_best(int n) {
    std::vector<int> ids(n);
    std::iota(ids.begin(), ids.end(), 0);
    while (ids.size() != 1) {
        ids = findLower(ids);
    }
    return ids[0];
}

Compilation message

prize.cpp: In function 'std::vector<int> findLower(std::vector<int>)':
prize.cpp:53:10: warning: variable 'relax' set but not used [-Wunused-but-set-variable]
   53 |     auto relax = [&](int i, std::vector<int> &ans) {
      |          ^~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	2116 KB	Output is correct
2	Correct	6 ms	2084 KB	Output is correct
3	Correct	12 ms	2012 KB	Output is correct
4	Correct	14 ms	1948 KB	Output is correct
5	Correct	13 ms	1944 KB	Output is correct
6	Correct	11 ms	1944 KB	Output is correct
7	Correct	9 ms	2000 KB	Output is correct
8	Correct	10 ms	1944 KB	Output is correct
9	Correct	11 ms	2088 KB	Output is correct
10	Correct	13 ms	2132 KB	Output is correct

Subtask #2

71.59 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	2000 KB	Output is correct
2	Correct	7 ms	2120 KB	Output is correct
3	Correct	8 ms	2120 KB	Output is correct
4	Correct	13 ms	2128 KB	Output is correct
5	Correct	9 ms	1948 KB	Output is correct
6	Correct	13 ms	1940 KB	Output is correct
7	Correct	13 ms	2044 KB	Output is correct
8	Correct	12 ms	1992 KB	Output is correct
9	Correct	18 ms	2072 KB	Output is correct
10	Correct	10 ms	2012 KB	Output is correct
11	Correct	12 ms	2092 KB	Output is correct
12	Correct	9 ms	2100 KB	Output is correct
13	Correct	15 ms	2004 KB	Output is correct
14	Correct	9 ms	544 KB	Output is correct
15	Partially correct	60 ms	2472 KB	Partially correct - number of queries: 5439
16	Partially correct	48 ms	2480 KB	Partially correct - number of queries: 5648
17	Partially correct	38 ms	2540 KB	Partially correct - number of queries: 5662
18	Partially correct	45 ms	2476 KB	Partially correct - number of queries: 5691
19	Partially correct	57 ms	2464 KB	Partially correct - number of queries: 5430
20	Correct	45 ms	1460 KB	Output is correct
21	Partially correct	56 ms	2456 KB	Partially correct - number of queries: 5628
22	Correct	50 ms	2332 KB	Output is correct
23	Correct	13 ms	1948 KB	Output is correct
24	Correct	16 ms	1996 KB	Output is correct
25	Partially correct	26 ms	2508 KB	Partially correct - number of queries: 5302
26	Partially correct	62 ms	2404 KB	Partially correct - number of queries: 5249
27	Correct	8 ms	1996 KB	Output is correct
28	Partially correct	54 ms	2428 KB	Partially correct - number of queries: 5238
29	Correct	53 ms	2332 KB	Output is correct
30	Partially correct	57 ms	2516 KB	Partially correct - number of queries: 5635
31	Partially correct	33 ms	2540 KB	Partially correct - number of queries: 5605
32	Correct	12 ms	2092 KB	Output is correct
33	Correct	1 ms	208 KB	Output is correct
34	Partially correct	64 ms	2460 KB	Partially correct - number of queries: 5688
35	Correct	7 ms	2080 KB	Output is correct
36	Partially correct	43 ms	2636 KB	Partially correct - number of queries: 5673
37	Correct	18 ms	2164 KB	Output is correct
38	Correct	10 ms	1948 KB	Output is correct
39	Partially correct	28 ms	2544 KB	Partially correct - number of queries: 5637
40	Partially correct	52 ms	2492 KB	Partially correct - number of queries: 5041
41	Partially correct	56 ms	2560 KB	Partially correct - number of queries: 5672
42	Partially correct	62 ms	2452 KB	Partially correct - number of queries: 5672
43	Partially correct	46 ms	2456 KB	Partially correct - number of queries: 5538
44	Partially correct	29 ms	2556 KB	Partially correct - number of queries: 5686
45	Partially correct	61 ms	2456 KB	Partially correct - number of queries: 5256
46	Partially correct	53 ms	2504 KB	Partially correct - number of queries: 5702
47	Partially correct	60 ms	2504 KB	Partially correct - number of queries: 5335
48	Partially correct	49 ms	2528 KB	Partially correct - number of queries: 5674
49	Partially correct	47 ms	2516 KB	Partially correct - number of queries: 5709
50	Partially correct	49 ms	2528 KB	Partially correct - number of queries: 5672
51	Partially correct	42 ms	2540 KB	Partially correct - number of queries: 5671
52	Partially correct	63 ms	2456 KB	Partially correct - number of queries: 5697
53	Correct	14 ms	1956 KB	Output is correct
54	Partially correct	65 ms	2460 KB	Partially correct - number of queries: 5630
55	Partially correct	52 ms	2580 KB	Partially correct - number of queries: 5696
56	Partially correct	64 ms	2536 KB	Partially correct - number of queries: 5702
57	Partially correct	55 ms	2592 KB	Partially correct - number of queries: 5664
58	Partially correct	30 ms	2544 KB	Partially correct - number of queries: 5661
59	Partially correct	50 ms	2460 KB	Partially correct - number of queries: 5686
60	Partially correct	56 ms	2476 KB	Partially correct - number of queries: 5651
61	Correct	14 ms	1932 KB	Output is correct
62	Correct	15 ms	2004 KB	Output is correct
63	Correct	17 ms	1948 KB	Output is correct
64	Correct	9 ms	2072 KB	Output is correct
65	Correct	13 ms	2000 KB	Output is correct
66	Correct	9 ms	2080 KB	Output is correct
67	Correct	14 ms	2000 KB	Output is correct
68	Correct	14 ms	1952 KB	Output is correct
69	Correct	14 ms	1980 KB	Output is correct
70	Correct	7 ms	2132 KB	Output is correct
71	Partially correct	69 ms	2584 KB	Partially correct - number of queries: 5841
72	Correct	23 ms	2028 KB	Output is correct
73	Partially correct	60 ms	2484 KB	Partially correct - number of queries: 5778
74	Partially correct	48 ms	2532 KB	Partially correct - number of queries: 5805
75	Correct	10 ms	1976 KB	Output is correct
76	Partially correct	47 ms	2444 KB	Partially correct - number of queries: 5193
77	Partially correct	51 ms	2644 KB	Partially correct - number of queries: 5776
78	Correct	15 ms	2000 KB	Output is correct
79	Correct	22 ms	2208 KB	Output is correct
80	Partially correct	57 ms	2528 KB	Partially correct - number of queries: 5750
81	Partially correct	59 ms	2564 KB	Partially correct - number of queries: 5779
82	Partially correct	62 ms	2452 KB	Partially correct - number of queries: 5723
83	Correct	12 ms	2000 KB	Output is correct
84	Correct	34 ms	2388 KB	Output is correct
85	Partially correct	28 ms	2464 KB	Partially correct - number of queries: 5786
86	Correct	12 ms	1976 KB	Output is correct
87	Correct	6 ms	2080 KB	Output is correct
88	Correct	10 ms	1988 KB	Output is correct
89	Correct	14 ms	1984 KB	Output is correct
90	Correct	16 ms	2064 KB	Output is correct
91	Correct	11 ms	2000 KB	Output is correct
92	Correct	14 ms	2000 KB	Output is correct
93	Correct	15 ms	2072 KB	Output is correct
94	Correct	17 ms	2024 KB	Output is correct
95	Correct	15 ms	2108 KB	Output is correct
96	Correct	18 ms	1996 KB	Output is correct
97	Correct	9 ms	1988 KB	Output is correct