oj.uz

Submission #1080478

# Submission time Handle Problem Language Result Execution time Memory
1080478 2024-08-29T10:19:38 Z TB_ The Big Prize (IOI17_prize) C++17
0 / 100
 56 ms 76628 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);

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; 
    }
};

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;

    }
}

Compilation message

prize.cpp: In member function 'long long int Node::query(long long int)':
prize.cpp:54:12: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   54 |         ll res;
      |            ^~~
prize.cpp:61:13: warning: control reaches end of non-void function [-Wreturn-type]
   61 |         val = lnode->val+rnode->val;
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 76628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 76584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -