oj.uz

Submission #781915

# Submission time Handle Problem Language Result Execution time Memory
781915 2023-07-13T13:18:22 Z TheSahib The Big Prize (IOI17_prize) C++14
20 / 100
 30 ms 9860 KB 
#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 <= 5000){
        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];
    while(true){
        int l = 1, r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            a = query(mid);

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

            a[0] -= ask(1, mid - 1);
            a[1] -= ask(mid + 1, n);

            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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 4 ms 4944 KB Output is correct
7 Correct 2 ms 4996 KB Output is correct
8 Correct 3 ms 5000 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4992 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 5000 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 3 ms 4996 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5364 KB Output is correct
13 Correct 3 ms 4944 KB Output is correct
14 Correct 9 ms 5092 KB Output is correct
15 Correct 16 ms 5716 KB Output is correct
16 Correct 10 ms 5120 KB Output is correct
17 Correct 30 ms 5800 KB Output is correct
18 Correct 2 ms 4944 KB Output is correct
19 Correct 23 ms 5752 KB Output is correct
20 Correct 18 ms 5200 KB Output is correct
21 Correct 27 ms 5500 KB Output is correct
22 Correct 25 ms 5672 KB Output is correct
23 Runtime error 7 ms 9860 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -