oj.uz

Submission #781876

# Submission time Handle Problem Language Result Execution time Memory
781876 2023-07-13T12:26:33 Z TheSahib The Big Prize (IOI17_prize) C++14
20 / 100
 3 ms 5072 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 <= 4){
        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];
    int b = 0;
    while(true){
        b++;
        int l = 1, r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            a = query(mid);
            a[0] -= ask(1, mid - 1);
            a[1] -= ask(mid + 1, n);

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


            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 4992 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 3 ms 4996 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 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 3 ms 4944 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4976 KB Output is correct
6 Correct 2 ms 4996 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 5000 KB Output is correct
9 Correct 2 ms 4996 KB Output is correct
10 Correct 2 ms 4896 KB Output is correct
11 Incorrect 3 ms 5028 KB answer is not correct
12 Halted 0 ms 0 KB -