Submission #837066

#	Time	Username	Problem	Language	Result	Execution time	Memory
837066		kamelfanger83	The Big Prize (IOI17_prize)	C++14	97.94 / 100	50 ms	8508 KiB

prize

#include <vector>
#include <cassert>

#include "prize.h"

using namespace std;

struct Segtree{
    vector<int> cache;
    Segtree(int n){
        cache.resize(4 * n);
    }
    void buildao(int l, int r, int i){
        cache[i] = r-l;
        if (l + 1 < r){
            int m = l + (r-l)/2;
            buildao(l, m, i*2+1);
            buildao(m, r, i*2+2);
        }
    }
    int update(int l, int r, int i, int ui, int ux){
        if (ui < l || r <= ui) return cache[i];
        if (l + 1 == r) return cache[i] = ux;
        int m = l + (r-l)/2;
        return cache[i] = update(l, m, i*2+1, ui, ux) + update(m, r, i*2+2, ui, ux);
    }
    int query(int l, int r, int i, int ql, int qr){
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return cache[i];
        int m = l + (r-l)/2;
        return query(l, m, i*2+1, ql, qr) + query(m, r, i*2+2, ql, qr);
    }
    int findi (int l, int r, int i, int sum){
        if (l + 1 == r) {
            if (cache[i] > sum) return l;
            return r;
        }
        int m = l + (r-l)/2;
        if (cache[i*2+1] > sum) return findi(l, m, i*2+1, sum);
        else return findi(m, r, i*2+2, sum - cache[i*2+1]);
    }
};

vector<int> queried; int maxsum = 0;
Segtree segtree (1);
int N;

vector<vector<int>> ans;

vector<int> myask(int i){
    if (ans[i].size()) return ans[i];
    return ans[i] = ask(i);
}

int find(int fake_l, int fake_r, int suml, int sumr, int sumh){
    if (fake_l >= fake_r) {
        //assert(sumh == 0);
        return -1;
    }
    if (sumh == 0) return -1;
    int fake_m = (fake_l + fake_r) / 2;
    int real_m = segtree.findi(0, N, 0, fake_m);
    auto ans = myask(real_m);
    int l = ans[0], r = ans[1];
    if (l + r == 0) return real_m;
    else if (l + r > maxsum){
        for (int i : queried) segtree.update(0, N, 0, i, 0);
        queried = {real_m};
        maxsum = l + r;
        return -2;
    }
    else if (l + r < maxsum){
        segtree.update(0, N, 0, real_m, 0);
        int middle = 1;
        fake_r--;
        for (int dev = 1;; ++dev) {
            if (fake_m < fake_r) {
                int real_m = segtree.findi(0, N, 0, fake_m);
                auto ans = myask(real_m);
                int l = ans[0], r = ans[1];
                if (l + r == 0) return real_m;
                if (l + r > maxsum) {
                    for (int i : queried) segtree.update(0, N, 0, i, 0);
                    queried = {real_m};
                    maxsum = l + r;
                    return -2;
                }
                if (l + r == maxsum){
                    int r1 = find(fake_l, fake_m, suml, r + middle, l - suml - middle);
                    int r2 = find(fake_m + 1 - (l - suml - middle), fake_r - (l - suml - middle), l, sumr, r - sumr);
                    if (r1 != -1) return r1;
                    return r2;
                }
                segtree.update(0, N, 0, real_m, 0);
                middle++;
                fake_r--;
            }
            else {
                return find(fake_l, fake_m, suml, sumr + middle, sumh - middle);
            }
        }
    }
    int real_l = segtree.findi(0, N, 0, fake_l), real_r = segtree.findi(0, N, 0, fake_r - 1) + 1;
    int donel = real_m - real_l - segtree.query(0, N, 0, real_l, real_m), doner = real_r - real_m - 1 - segtree.query(0, N, 0, real_m + 1, real_r);
    int al = l - suml - donel;
    int ar = r - sumr - doner;
    if (al > 0){
        int ret = find(fake_l, fake_m, suml, r, al);
        if (ret != -1) return ret;
    }
    if (ar > 0){
        int ret = find(fake_m - al + 1, fake_r - al, l, sumr, ar);
        if (ret != -1) return ret;
    }
    return -1;
}

int find_best(int n){
    ans.resize(n);
    maxsum = 0;
    for (int i = 0; i * i < n; ++i) {
        auto ans = myask(i);
        int l = ans[0], r = ans[1];
        if (l + r > maxsum) maxsum = l + r;
    }
    segtree = Segtree (n);
    N = n;
    queried.clear();
    segtree.buildao(0, n, 0);
    int ret = -2;
    while (ret == -2){
        ret = find(0, segtree.cache[0], segtree.findi(0, N, 0, 0), N - segtree.findi(0, N, 0, segtree.cache[0] - 1) - 1, -1);
    }
    //assert(segtree.cache[0] + maxsum == N);
    return ret;
}

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