Submission #820791

#	Time	Username	Problem	Language	Result	Execution time	Memory
820791		vjudge1	The Big Prize (IOI17_prize)	C++17	100 / 100	53 ms	7824 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

struct fenwick {
    vector<int> v;
    fenwick(int N) : v(N + 1, 0) {}
    void upd(int x, int g) {
        while (x < v.size()) {
            v[x] += g;
            x += x & -x;
        }
    }
    int get(int x) {
        int res = 0;
        while (x > 0) {
            res += v[x];
            x -= x & -x;
        }
        return res;
    }
};

int find_best(int n)
{
    #define fi first
    #define se second

    vector<int> to_ask;
    queue<pair<int, int>> q;
    fenwick tree(n + 10);

    q.push({0, n - 1});
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        if (p.fi > p.se) {
            continue;
        }
        int m = (p.fi + p.se) / 2;
        to_ask.push_back(m);
        q.push({p.fi, m - 1});
        q.push({m + 1, p.se});
    }

    map<int, set<int>> s;
    auto upd = [&](int sum, int i) -> tuple<int, int> {
        s[sum].insert(i);
        auto p = s[sum].find(i);
        int l = -1, r = -1;
        if (p != s[sum].begin()) {
            p--;
            l = *p;
            p++;
        }
        p++;
        if (p != s[sum].end()) {
            r = *p;
        }
        return {l, r};
    };

    vector<vector<int>> asked(n + 1);
    for (int i: to_ask) {
        if (tree.get(i + 1) > 0) {
            continue;
        }
        auto ans = ask(i);
        if (ans[0] + ans[1] == 0) {
            return i;
        }
        asked[i] = ans;
        auto [l, r] = upd(ans[0] + ans[1], i);
        if (l != -1 && asked[i][0] - asked[l][0] == 0) {
            tree.upd(l + 1, 1);
            tree.upd(i + 1, -1);
        }
        if (r != -1 && asked[r][0] - asked[i][0] == 0) {
            tree.upd(i + 1, 1);
            tree.upd(r + 1, -1);
        }
    }
}

Compilation message (stderr)

prize.cpp: In member function 'void fenwick::upd(int, int)':
prize.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         while (x < v.size()) {
      |                ~~^~~~~~~~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:31:17: warning: control reaches end of non-void function [-Wreturn-type]
   31 |     vector<int> to_ask;
      |                 ^~~~~~

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