oj.uz

Submission #1080489

# Submission time Handle Problem Language Result Execution time Memory
1080489 2024-08-29T10:26:36 Z TB_ The Big Prize (IOI17_prize) C++17
20 / 100
 41 ms 38220 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

typedef vector<ll> vl;
typedef vector<vl> vvl;

int find_best(int n);
std::vector<int> ask(int i);
// std::vector<int> ask(int i){
//     ll gaah = 2;
//     if(i==gaah) return {0, 0};
//     else if(i>gaah) return {1, 0};
//     else return {0, 1};
// }

ll valval = 1;

struct Node{
    Node *lnode, *rnode;
    ll l, r, val = valval;
    Node(ll l, ll r) : l(l), r(r){
        if(r-l>1){
            ll mid = (r+l) / 2;
            lnode = new Node(l, mid);
            rnode = new Node(mid, r);
            val = lnode->val+rnode->val;
        }
    }

    void update2(ll lo, ll hi){
        if(r <= lo || hi <= l) return;
        if(r <= hi && lo <= l){
            val = 1;
            return;
        }
        lnode->update2(lo, hi);rnode->update2(lo, hi); 
        val = lnode->val+rnode->val;
    }

    ll sumQuery(ll lo, ll hi){
        if(r <= lo || hi <= l) return 0;
        if(r <= hi && lo <= l) return val;
        return lnode->sumQuery(lo, hi)+rnode->sumQuery(lo, hi); 
    }

    ll query(ll x){
        if(r-l == 1){
            val = 0;
            return l;
        }
        ll res;
        if(lnode->val>x) res = lnode->query(x);
        else{
            x-=lnode->val;
            res = rnode->query(x);
        }
        val = lnode->val+rnode->val;
        return res;
    }
};

int find_best(int n){
    ll prething = -1;
    mt19937 rng(42);
    fo(i, 500){
        ll temp = rng()%n;
        vector<int> res = ask(temp);
        if(res[0] ==0 && res[1] == 0){
            return temp;
        }
        prething = max(prething, (ll)res[0]+res[1]);
    } 
    Node st(0, n);
    valval = 0;
    Node st2(0, n);
    while(1){
        ll lo = 0;
        ll hi = n;
        while(hi-lo>1){
            ll mid = (hi+lo) / 2; 
            ll a = st.sumQuery(0, lo);
            ll b = st.sumQuery(0, hi);
            ll pos = st.query((a+b)/2);
            vector<int> res = ask(mid);
            if(res[0] ==0 && res[1] == 0){
                return mid;
            }
            if(res[0]+res[1] <prething){
                st2.update2(pos, pos+1);
                break;
            }
            res[0]-=st2.sumQuery(0, pos);
            if(res[0]) hi = mid;
            else lo = mid+1;
        }
        return lo;

    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 38220 KB Output is correct
2 Correct 31 ms 37976 KB Output is correct
3 Correct 31 ms 37968 KB Output is correct
4 Correct 41 ms 37796 KB Output is correct
5 Correct 31 ms 37968 KB Output is correct
6 Correct 28 ms 37968 KB Output is correct
7 Correct 31 ms 37976 KB Output is correct
8 Correct 29 ms 37976 KB Output is correct
9 Correct 27 ms 37976 KB Output is correct
10 Correct 30 ms 37788 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 37976 KB Output is correct
2 Correct 28 ms 37968 KB Output is correct
3 Correct 28 ms 37976 KB Output is correct
4 Correct 29 ms 37976 KB Output is correct
5 Correct 28 ms 37856 KB Output is correct
6 Correct 30 ms 37976 KB Output is correct
7 Correct 28 ms 37968 KB Output is correct
8 Correct 30 ms 37968 KB Output is correct
9 Correct 29 ms 37972 KB Output is correct
10 Correct 29 ms 37968 KB Output is correct
11 Incorrect 31 ms 37968 KB answer is not correct
12 Halted 0 ms 0 KB -