oj.uz

Submission #781856

# Submission time Handle Problem Language Result Execution time Memory
781856 2023-07-13T12:03:01 Z TheSahib The Big Prize (IOI17_prize) C++14
0 / 100
 1000 ms 1048576 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 != r) 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){
        for (int i = 1; i <= n; i++)
        {
            vector<int> a = query(i);
            if(a[0] + a[1] == 0){
                return i - 1;
            }
        }
    }
    srand(time(0));
    vector<int> a = query(intRand() % n + 1);
    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;
            }

            if(a[0] + a[1] < cnt){
                update(mid, 1);
                break;
            }

            a[0] -= ask(1, mid - 1);
            a[1] -= ask(mid + 1, n);
            if(a[1] > 0){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1243 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 884 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -