Submission #619393

#	Time	Username	Problem	Language	Result	Execution time	Memory
619393		Sergio_2357	The Big Prize (IOI17_prize)	C++17	20 / 100	192 ms	2532 KiB

prize

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

using namespace std;

typedef vector<int> vi;

struct SegTree {
    int n;
    vi v;
    void update(int i, int l, int h, int idx, int val)
    {
        //cout << i << ' ' << idx << ' ' << l << ' ' << h << endl;
        if (h - l <= 1) {
            v[i] = val;
            return;
        }
        int m = (h - l) / 2 + l;
        if (idx < m)
            update(2 * i, l, m, idx, val);
        else
            update(2 * i + 1, m, h, idx, val);
        v[i] = v[2 * i] + v[2 * i + 1];
    }
    void update(int i, int val)
    {
        update(1, 0, n, i, val);
    }
    int query(int i, int l, int h, int ql, int qh)
    {
        if (h <= ql || qh <= l)
            return 0;
        if (l <= ql && qh <= h)
            return v[i];
        int m = (h - l) / 2 + l;
        return query(2 * i, l, m, ql, qh) + query(2 * i + 1, m, h, ql, qh);
    }
    int query(int l, int h)
    {
        return query(1, 0, n, l, h);
    }
    SegTree() { }
    SegTree(int sz)
    {
        n = 1;
        while (n < sz)
            n *= 2;
        v = vi(2 * n + 1, 0);
    }
};

int n;
SegTree st;
set<int> nl;
map<int, vi> qr;
int llc = 0;
int res = -1;

vi ask2(int i)
{
    //cout << i << endl;
    if (qr.count(i))
        return qr[i];
    qr[i] = ask(i);
    return qr[i];
}

int cask(int i)
{
    int p1, p2;
    p1 = p2 = i;
    while (nl.count(p1))
        p1--;
    while (nl.count(p2))
        p2++;
    if (p1 < 0)
        p1 = p2;
    if (p2 >= n)
        p2 = p1;
    if (abs(i - p1) > abs(i - p2))
        i = p1;
    else
        i = p2;
    auto p = ask2(i);
    if (p[0] + p[1] == 0)
        res = i;
    if (p[0] + p[1] < llc) {
        nl.insert(i);
        st.update(i, 1);
        return 2;
    }
    int l = p[0] - st.query(0, i);
    int r = p[1] - st.query(i, n);
    return l < r;
}

int find_best(int n_)
{
    n = n_;
    st = SegTree(n + 1);
    for (int i = 0; i < min(n, 500); i++) {
        auto p = ask2(i);
        llc = max(llc, p[0] + p[1]);
        //if (p[0] + p[1] == 0)
        //    return i;
    }
    int marp = 100000;
    while (res == -1 && marp--) {
        int l = 0;
        int h = n - 1;
        bool found = false;
        int ps = nl.size();
        while (l < h - 2) {
            int m = (h - l) / 2 + l;
            int r = cask(m);
            if (r == 2) {
                if (nl.size() == ps)
                    res = -2;
                found = true;
                break;
            }
            if (r)
                l = m;
            else
                h = m;
        }
        if (!found)
            for (int i = l; i <= h; i++)
                cask(i);
        //if (nl.size() == ps)
        //    res = -2;
    }
    return res;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:117:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |                 if (nl.size() == ps)
      |                     ~~~~~~~~~~^~~~~

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