Submission #860917

#	Time	Username	Problem	Language	Result	Execution time	Memory
860917		TahirAliyev	The Big Prize (IOI17_prize)	C++17	97.42 / 100	70 ms	16476 KiB

prize

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

using namespace std;

#define ll long long
#define pii pair<int, int>

const int MAX = 2e5 + 5, BLOCK = 500;

int tree[MAX];
vector<int> H[MAX];
int det = 0;

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

int q(int l, int r){
    if(l != 1) return q(1, r) - q(1, l - 1);
    int res = 0;
    for(int i = r; i > 0; i -= (-i & i)){
        res += tree[i];
    }
    return res;
}

int find_best(int n){
    for(int i = 0; i < min(BLOCK, n); i++){
        H[i] = ask(i);
        if(H[i][0] + H[i][1] == 0) return i;
        det = max(det, H[i][0] + H[i][1]);
    }
    set<int> s;
    for(int i = 0; i < n; i++){
        s.insert(i);
    }
    for(int k = 1; k <= det; k++){
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            auto itr = s.lower_bound(mid);
            if(itr == s.end()) --itr;
            mid = *itr;
            if(H[mid].empty()){
                H[mid] = ask(mid);
            }
            if(H[mid][0] + H[mid][1] == 0) return mid;
            if(H[mid][0] + H[mid][1] != det){
                update(mid + 1, 1);
                s.erase(mid);
                break;
            }
            if(H[mid][1] - q(mid + 2, n)){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:36:14: warning: control reaches end of non-void function [-Wreturn-type]
   36 |     set<int> s;
      |              ^

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