Submission #590746

#	Time	Username	Problem	Language	Result	Execution time	Memory
590746		alirezasamimi100	The Big Prize (IOI17_prize)	C++17	0 / 100	1711 ms	1048576 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int ans = -1, cnt = 0, mx = 0;

vector<int> vec[500],wh;
map<int,int> rv;

vector<int> doask(int i, int k = 0){
    vector<int> v;
    if(rv.count(i) && !k) v = vec[rv[i]];
    else v = ask(i);
    if(v[0] == 0 && v[1] == 0) ans = i;
    return v;
}

void solve(int l, int r, int x){
    if(ans != -1) return;
    int m1 = (l + r) >> 1, t = 0, m2 = m1 + 1, f;
    vector<int> v;
    while(m1 >= l || m2 < r){
        if(m1 >= l){
            v = doask(m1);
            m1--;
            if(v[0] + v[1] == mx){
                f = 0;
                break;
            }
            t++;
        }
        if(m2 < r){
            v = doask(m2);
            m2++;
            if(v[0] + v[1] == mx){
                f = 1;
                break;
            }
            t++;
        }
    }
    if(!f){
        if(l <= m1 && v[0] > cnt) solve(l, m1 + 1, v[1]);
        cnt += t;
        if(m2 < r && v[1] - x - t > 0) solve(m2, r, x);
    }else{
        if(l <= m1 && v[0] > cnt + t) solve(l, m1 + 1, v[1] + t);
        cnt += t;
        if(m2 < r && v[1] - x > 0) solve(m2, r, x);
    }
}
int find_best(int n) {
    queue<pair<int,int>> q;
    q.push({0,n});
    while((int)wh.size()<=min(n,500)){
        int l=q.front().first,r=q.front().second,m=(l+r)>>1;
        if(!rv.count(m)){
            rv[m]=wh.size();
            wh.pb(m);
        }
        if(r-l>1){
            q.push({l,m});
            q.push({m,r});
        }
    }
    for(int i = 0; i < min(n, 500); i++){
        vec[i] = doask(wh[i], 1);
        if(vec[i][0] + vec[i][1] > mx) mx = vec[i][0] + vec[i][1];
    }
    int x = 0;
    while(n){
        vector<int> v = doask(n - 1);
        n--;
        if(v[0] + v[1] == mx) break;
        x++;
    }
    solve(0, n, x);
    return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void solve(int, int, int)':
prize.cpp:47:5: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     if(!f){
      |     ^~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80