oj.uz

Submission #790505

# Submission time Handle Problem Language Result Execution time Memory
790505 2023-07-22T18:08:26 Z skittles1412 The Big Prize (IOI17_prize) C++17
0 / 100
 1000 ms 1856 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

vector<int> ask(int i);

constexpr int maxn = 2e5 + 5;

struct Q {
    pair<int, int> cache[maxn];

    Q() {
        memset(cache, -1, sizeof(cache));
    }

    pair<int, int> query(int ind) {
        auto& ans = cache[ind];
        if (ans.first != -1) {
            return ans;
        }
        auto cv = ask(ind);
        assert(sz(cv) == 2);
        ans = {cv[0], cv[1]};
        return ans;
    }
} Q;

struct Solver {
    bool bad = false;
    int opt_ge, found_opt = -1, ans = -1;

    Solver(int n, int opt_ge) : opt_ge(opt_ge) {
        solve(0, n - 1, 0, 0);
    }

    void solve(int l, int r, int cl, int cr) {
        if (ans != -1 || bad || l > r) {
            return;
        }
        for (int mid = (l + r) / 2, small = 0; mid <= r; mid++) {
            auto [ql, qr] = Q.query(mid);
            if (!ql && !qr) {
                ans = mid;
                return;
            }
            if (ql + qr < opt_ge) {
                small++;
                continue;
            }
            if (ql + qr > opt_ge) {
                bad = true;
                found_opt = max(found_opt, ql + qr);
                return;
            }
            solve(mid + 1, r, ql, cr);
            solve(l, (l + r) / 2 - 1, cl, qr + small);
        }
    }
};

int find_best(int n) {
    int opt_ge = 0;
    while (true) {
        Solver s(n, opt_ge);
        if (s.ans != -1) {
            return s.ans;
        }
        assert(s.bad);
        opt_ge = s.found_opt;
    }
}

Compilation message

prize.cpp: In constructor 'Q::Q()':
prize.cpp:35:40: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   35 |         memset(cache, -1, sizeof(cache));
      |                                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/extc++.h:32,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 1856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 1856 KB Time limit exceeded
2 Halted 0 ms 0 KB -