oj.uz

Submission #1080523

# Submission time Handle Problem Language Result Execution time Memory
1080523 2024-08-29T10:43:49 Z TB_ The Big Prize (IOI17_prize) C++17
20 / 100
 1000 ms 37976 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};
//     if(i==0) return {0, 3};
//     if(i==1) return {0, 0};
//     if(i==2) return {1, 0};
//     if(i==3) return {2, 1};
//     if(i==4) return {2, 1};
//     if(i==5) return {1, 0};
//     else return {3, 0};
// }

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 co = 0;
    ll prething = -1;
    mt19937 rng(42);
    fo(i, 500){
        ll temp = rng()%n;
        co++;
        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){
        // deb("gahh");
        ll lo = 0;
        ll hi = n;
        while(hi-lo>1){
            if(co>9500) while(1){}
            ll a = st.sumQuery(0, lo);
            ll b = st.sumQuery(0, hi);
            ll pos = st.query((a+b)/2);
            co++;
            vector<int> res = ask(pos);
            // deb(pos);
            if(res[0] ==0 && res[1] == 0){
                return pos;
            }
            if(res[0]+res[1] <prething){
                st2.update2(pos, pos+1);
                break;
            }
            res[0]-=st2.sumQuery(0, pos);
            if(res[0]) hi = pos;
            else lo = pos+1;
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 37968 KB Output is correct
2 Correct 30 ms 37968 KB Output is correct
3 Correct 30 ms 37968 KB Output is correct
4 Correct 30 ms 37940 KB Output is correct
5 Correct 32 ms 37968 KB Output is correct
6 Correct 28 ms 37812 KB Output is correct
7 Correct 27 ms 37808 KB Output is correct
8 Correct 31 ms 37900 KB Output is correct
9 Correct 27 ms 37968 KB Output is correct
10 Correct 30 ms 37968 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37976 KB Output is correct
2 Correct 29 ms 37892 KB Output is correct
3 Correct 26 ms 37968 KB Output is correct
4 Correct 30 ms 37968 KB Output is correct
5 Correct 33 ms 37808 KB Output is correct
6 Correct 28 ms 37976 KB Output is correct
7 Correct 32 ms 37968 KB Output is correct
8 Correct 38 ms 37968 KB Output is correct
9 Correct 29 ms 37964 KB Output is correct
10 Correct 34 ms 37808 KB Output is correct
11 Correct 31 ms 37756 KB Output is correct
12 Correct 33 ms 37976 KB Output is correct
13 Correct 32 ms 37976 KB Output is correct
14 Correct 7 ms 4184 KB Output is correct
15 Correct 35 ms 37960 KB Output is correct
16 Partially correct 85 ms 37976 KB Partially correct - number of queries: 8979
17 Correct 31 ms 37968 KB Output is correct
18 Execution timed out 3056 ms 37752 KB Time limit exceeded
19 Halted 0 ms 0 KB -