Submission #1161564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161564		thangdz2k7	커다란 상품 (IOI17_prize)	C++20	100 / 100	13 ms	2056 KiB

prize

#include <bits/stdc++.h>

using namespace std;
using pii = pair <int, int>;

#ifdef ONLINE_JUDGE
#include "prize.h"
#else
vector <int> ask(int i);
#endif // ONLINE_JUDGE

int find_best(int n){

    try {

    vector <pii> ans(n);
    int rt = -1;

    auto get = [&](int x) -> void {
        if (ans[x].first || ans[x].second) return;

        vector <int> o = ask(x);
        if (!o[0] && !o[1])
            throw(x);

        ans[x] = {o[0], o[1]};
    };

    auto g = [&](int x) -> int {
        get(x);
        return ans[x].first + ans[x].second;
    };

    int mx = 0, l, r;

    for (l = 0; l < min(n, 500); ++ l){
        get(l);
        mx = max(mx, ans[l].first + ans[l].second);

        if (mx > 50) break;
    }

    for (l = 0; g(l) < mx; ++ l);
    for (r = n - 1; g(r) < mx; -- r);

    function <void (int, int, int, int)> dnc = [&](int l, int r, int pl, int pr) -> void {
        if (pl == pr) return;

        int mid = l + r >> 1, m = mid;
        while (m >= l && g(m) < mx) m --;

        if (m >= l) dnc(l, m, pl, ans[m].first);
        dnc(mid + 1, r, m >= l ? ans[m].first + mid - m : pl + mid - l + 1, pr);
    };

    dnc(l, r, ans[l].first, ans[r].first);

    } catch (int x){
        return x;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

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