Submission #1138209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138209		anmattroi	The Big Prize (IOI17_prize)	C++17	0 / 100	16 ms	5608 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;

int N;
int st[4*maxn];
constexpr int B = 450;

inline constexpr int csk(const int &u) {return u/B;}
inline constexpr int csd(const int &u) {return u*B;}
inline constexpr int csc(const int &u) {return min(N, (u+1)*B);}

void upd(int u, int d, int r = 1, int lo = 0, int hi = N-1) {
    if (lo == hi) {
        st[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) upd(u, d, r<<1, lo, mid);
    else upd(u, d, r<<1|1, mid+1, hi);
    st[r] = st[r<<1] + st[r<<1|1];
}

int get(int u, int v, int r = 1, int lo = 0, int hi = N-1) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return st[r];
    int mid = (lo + hi) >> 1;
    return get(u, v, r<<1, lo, mid) + get(u, v, r<<1|1, mid+1, hi);
}

int it[4*maxn];

void build(int r = 1, int lo = 0, int hi = N-1) {
    it[r] = hi-lo+1;
    if (lo == hi) return;
    int mid = (lo + hi) >> 1;
    build(r<<1, lo, mid);
    build(r<<1|1, mid+1, hi);
}

void update(int u, int d, int r = 1, int lo = 0, int hi = N-1) {
    if (lo == hi) {
        it[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(u, d, r<<1, lo, mid);
    else update(u, d, r<<1|1, mid+1, hi);
    it[r] = it[r<<1] + it[r<<1|1];
}

int bfind(int k, int r = 1, int lo = 0, int hi = N-1) {
    if (lo == hi) return lo;
    int mid = (lo + hi) >> 1, trai = it[r<<1];
    if (trai >= k) return bfind(k, r<<1, lo, mid);
    return bfind(k-trai, r<<1|1, mid+1, hi);
}

int get_sum(int u, int v, int r = 1, int lo = 0, int hi = N-1) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return it[r];
    int mid = (lo + hi) >> 1;
    return get_sum(u, v, r<<1, lo, mid) + get_sum(u, v, r<<1|1, mid+1, hi);
}

int find_best(int n) {
    N = n;
    for (int i = 1; i <= 4*N; i++) st[i] = 0;
    build();
    vector<int> nho;
    for (int i = 0; i < min(500, N); i++) {
        vector<int> res = ask(i);
        if (res[0] + res[1] == 0) return i;
        nho.emplace_back(res[0]+res[1]);
    }
    int p = max_element(nho.begin(), nho.end()) - nho.begin();
    for (int i = 0; i < p; i++) {
        upd(i, 1);
        update(i, 0);
    }
    vector<int> Old = ask(p);

    for (int i = p; i < csc(p); i++) {
        vector<int> res = ask(i);
        if (res[0] + res[1] == 0) return i;
        if (res[0] + res[1] != nho[p]) {
            update(i, 0);
            upd(i, 1);
        }
    }

    for (int o = csk(p)+1; o <= csk(n); o++) {
        while (1) {
            int lo = get_sum(p, csd(o)-1)+1, hi = get_sum(p, csc(o)-1);

            while (hi != lo) {
                int mid = (lo + hi) >> 1,
                    pos = bfind(mid);
                vector<int> res = ask(pos);
                if (res[0] + res[1] == 0) return pos;
                if (res[0] + res[1] != nho[p]) {
                    update(pos, 0);
                    upd(pos, 1);
                    break;
                }
                int How_many = Old[1] - res[1] - get(p, pos);
                if (How_many) hi = mid-1;
                else lo = mid+1;
            }
            if (lo != hi) continue;
            int pos = bfind(lo);
            vector<int> H = ask(pos);
            if (H[0] + H[1] == nho[p]) break;
            update(pos, 0);
            upd(pos, 1);
        }
    }

    return 0;
}
//10000 queries
//
//5 different gifts
/*
8
3 2 3 1 3 3 2 3
*/

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