oj.uz

Submission #1080548

# Submission time Handle Problem Language Result Execution time Memory
1080548 2024-08-29T10:51:58 Z TB_ The Big Prize (IOI17_prize) C++17
0 / 100
 1000 ms 37968 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 update(ll lo, ll hi){
        if(r <= lo || hi <= l) return;
        if(r <= hi && lo <= l){
            val = 0;
            return;
        }
        lnode->update(lo, hi);rnode->update(lo, hi); 
        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){
            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);
    map<ll, vector<int>> memo;
    while(1){
        // deb("gahh");
        ll lo = 0;
        ll hi = n;
        while(hi-lo>1){
            ll a = st.sumQuery(0, lo);
            ll b = st.sumQuery(0, hi);
            ll pos = st.query((a+b)/2);
            co++;
            vector<int> res;
            if(memo.count(pos)){
                res = memo[pos];
            }else{
                res = ask(pos);
                memo[pos] = res; 
            }
            // deb(pos);
            if(res[0] ==0 && res[1] == 0){
                return pos;
            }
            if(res[0]+res[1] <prething){
                st.update(pos, pos+1);
                st2.update2(pos, pos+1);
                break;
            }
            res[0]-=st2.sumQuery(0, pos);
            if(res[0]) hi = pos;
            else lo = pos+1;
        }
    }
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:76:12: warning: 'st.Node::lnode' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         if(lnode->val>x) res = lnode->query(x);
      |            ^~~~~
prize.cpp:79:19: warning: 'st.Node::rnode' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |             res = rnode->query(x);
      |                   ^~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 80.0

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