Submission #781876

#	Time	Username	Problem	Language	Result	Execution time	Memory
781876		TheSahib	The Big Prize (IOI17_prize)	C++14	20 / 100	3 ms	5072 KiB

prize

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

using namespace std;

const int MAX = 2e5 + 5;

int tree[MAX];

void update(int pos, int val){
    while(pos < MAX){
        tree[pos] += val;
        pos += pos & -pos;
    }
}

int ask(int l, int r){
    if(l != 1) return ask(1, r) - ask(1, l - 1);
    int ans = 0;
    while(r > 0){
        ans += tree[r];
        r -= r & -r;
    }
    return ans;
}

int intRand(){
    return (rand() << 15) + rand();
}

vector<int> mp[MAX];

vector<int> query(int i){
    if(mp[i].size()) return mp[i];
    return mp[i] = ask(i - 1);
}


int find_best(int n) {
    if(n <= 4){
        vector<int> order(n);
        iota(order.begin(), order.end(), 1);
        random_shuffle(order.begin(), order.end());
        for (int i:order)
        {
            vector<int> a = query(i);
            if(a[0] + a[1] == 0){
                return i - 1;
            }
        }
    }
    srand(time(0));
    int c = intRand() % n + 1;
    vector<int> a = query(c);
    int cnt = a[0] + a[1];
    int b = 0;
    while(true){
        b++;
        int l = 1, r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            a = query(mid);
            a[0] -= ask(1, mid - 1);
            a[1] -= ask(mid + 1, n);

            if(a[0] + a[1] == 0){
                return mid - 1;
            }


            if(a[0] + a[1] < cnt){
                update(mid, 1);
                cnt--;
                break;
            }

            if(a[1] > 0){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
    }
}

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