oj.uz

Submission #760528

# Submission time Handle Problem Language Result Execution time Memory
760528 2023-06-17T17:41:39 Z raysh07 The Big Prize (IOI17_prize) C++17
20 / 100
 8 ms 1572 KB 
#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){
        // 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;
// 	}
	assert(mx == 1);
	
	for (int i = 0; i < n; i++) a.push_back(i);
	
	while (true){
	    int get = find();
	    if (get > -1) return get;
	    return 0;
	}
	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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1476 KB Output is correct
2 Correct 6 ms 1480 KB Output is correct
3 Correct 3 ms 1480 KB Output is correct
4 Correct 3 ms 1472 KB Output is correct
5 Correct 6 ms 1440 KB Output is correct
6 Correct 5 ms 1448 KB Output is correct
7 Correct 4 ms 1480 KB Output is correct
8 Correct 6 ms 1452 KB Output is correct
9 Correct 4 ms 1440 KB Output is correct
10 Correct 4 ms 1392 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1472 KB Output is correct
2 Correct 6 ms 1448 KB Output is correct
3 Correct 6 ms 1456 KB Output is correct
4 Correct 6 ms 1572 KB Output is correct
5 Correct 5 ms 1480 KB Output is correct
6 Correct 6 ms 1480 KB Output is correct
7 Correct 3 ms 1480 KB Output is correct
8 Correct 6 ms 1432 KB Output is correct
9 Correct 5 ms 1480 KB Output is correct
10 Correct 3 ms 1480 KB Output is correct
11 Runtime error 3 ms 456 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -