Submission #836629

#	Time	Username	Problem	Language	Result	Execution time	Memory
836629		kamelfanger83	The Big Prize (IOI17_prize)	C++14	0 / 100	70 ms	5256 KiB

prize

#include <vector>

#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 (l <= ql && qr <= r) 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) return l;
        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;

int find(int fake_l, int fake_r, int suml, int sumr, int sumh){
    if (fake_l >= fake_r) return -1;
    int fake_m = (fake_l + fake_r) / 2;
    int real_m = segtree.findi(0, N, 0, fake_m);
    auto ans = ask(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 -1;
    }
    else if (l + r < maxsum){
        segtree.update(0, N, 0, real_m, 0);
        if (sumh == -1 || sumh > 1) return find(fake_l, fake_r - 1, suml, sumr, sumh - 1);
        return -1;
    }
    int real_l = segtree.findi(0, N, 0, fake_l), real_r = segtree.findi(0, N, 0, fake_r);
    int behindisl = real_m - real_l - segtree.query(0, N, 0, real_l, real_m);
    int behindisr = real_r - real_m - segtree.query(0, N, 0, real_m + 1, real_r);
    int al = l - suml - behindisl;
    int ar = r - sumr - behindisr;
    if (al > 0){
        int ret = find(fake_l, fake_m, suml, r, sumh - ar);
        if (ret != -1) return ret;
    }
    if (ar > 0){
        int ret = find(fake_m - l, fake_r - l, l, sumr, sumh - al);
        if (ret != -1) return ret;
    }
    return -1;
}

int find_best(int n){
    segtree = Segtree (n);
    N = n;
    segtree.buildao(0, n, 0);
    int ret = -1;
    while (ret == -1){
        ret = find(0, n, 0, 0, -1);
    }
    return ret;
}

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