Submission #582007

#	Time	Username	Problem	Language	Result	Execution time	Memory
582007		alirezasamimi100	The Big Prize (IOI17_prize)	C++17	97.41 / 100	54 ms	444 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];

vector<int> doask(int i, int k = 0){
    vector<int> v;
    if(i < 500 && !k) v = vec[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) {
    for(int i = 0; i < min(n, 500); i++){
        vec[i] = doask(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:46:5: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     if(!f){
      |     ^~

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