Submission #760524

#	Time	Username	Problem	Language	Result	Execution time	Memory
760524		raysh07	The Big Prize (IOI17_prize)	C++17	0 / 100	67 ms	1488 KiB

prize

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

const int N = 2e5 + 69;
vector <int> a;
int f[N], mx;
int n;

void upd(int x){
    x++;
    for (int i = x; i <= n; i += i & (-i)) f[i]++;
}

int query(int x){
    x++;
    int res = 0;
    for (int i = x; i; i -= i & (-i)) res += f[i];
    return res;
}

void report(int x){
    assert(false);
    upd(a[x]);
    a.erase(a.begin() + x);
}

int find(){
    int l = 0, r = a.size() - 1;
    
    while (l != r){
        int m = (l + r)/2;
        
        auto g = ask(a[m]);
        int g1 = query(a[m]);
        if (g[0] + g[1] < mx){
            if (g[0] + g[1] == 0) return a[m];
            report(m);
            return 0;
        }
        if (g1 < g[0]) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    
    auto g = ask(a[l]);
    if (g[0] + g[1] == 0) return a[l];
    report(l);
    return 0;
}

int find_best(int m) {
    n = m;
	for (int i = 0; i < min(n, 500); i++){
	    auto get = ask(i);
	    
	    mx = max(mx, get[0] + get[1]);
	}
	assert(mx == 1);
	
	for (int i = 0; i < n; i++) a.push_back(i);
	
	while (true){
	    int get = find();
	    if (get > 0) return get;
	}
	assert(false);
	return 0;
}

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