Submission #760530

#	Time	Username	Problem	Language	Result	Execution time	Memory
760530		raysh07	The Big Prize (IOI17_prize)	C++17	90 / 100	81 ms	2092 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){
    upd(a[x]);
    a.erase(a.begin() + x);
}

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

int find_best(int m) {
    n = m;
    vector<vector<int>> ok;
	for (int i = 0; i < min(n, 500); i++){
	    auto get = ask(i);
	    ok.push_back(get);
	    
	    mx = max(mx, get[0] + get[1]);
	}
	
// 	if (mx != 1){
// 	    cout << n << "\n";
// 	    for (auto x : ok){
// 	        for (auto y : x) cout << y << " ";
// 	        cout << "\n";
// 	    }
// 	    return 0;
// 	}
	
	for (int i = 0; i < n; i++) a.push_back(i);
	
	while (true){
	    int get = find();
	    if (get > -1) return get;
	}
	assert(false);
	return 0;
}

// int main(){
//     // int t; cin >> t;
    
//     // while (t--){
//     //     int n = 3 + rand() % 10;
//     //     int x = rand() % n;
        
//     //     a.clear();
//     //     mx = 0;
//     //     for (int i = 0; i <= n; i++) f[i] = 0, a1[i] = a2[i] = 0;
        
//     //     for (int i = 0; i < x; i++) a2[i] = 1;
//     //     for (int i = x + 1; i < n; i++) a1[i] = 1;
        
//     //     int get = find_best(n);
//     //     if (get != x){
//     //         cout << n << " " << x << "\n";
//     //         return 0;
//     //     }
//     // }
    
//     int n; cin >> n;
//     for (int i = 0; i < n; i++) cin >> a1[i];
//     for (int i = 0; i < n; i++) cin >> a2[i];
    
//     cout << find_best(n);
//     return 0;
// }

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