Submission #136130

#	Time	Username	Problem	Language	Result	Execution time	Memory
136130		alexandra_udristoiu	The Big Prize (IOI17_prize)	C++14	96.92 / 100	58 ms	392 KiB

prize

#include<iostream>
#include<vector>
#include<cmath>
#include "prize.h"
using namespace std;
static int nr, x;
void solve(int p, int u, int nrp, int nru){
    if(p > u || nrp + nru == nr){
        return;
    }
    vector<int> a;
    int mid, m;
    if(p == u){
        a = ask(p);
        if(a[0] + a[1] == 0){
            x = p;
        }
        return;
    }
    mid = (p + u) / 2;
    m = mid;
    while(m >= p){
        a = ask(m);
        if(a[0] + a[1] == 0){
            x = m;
            return;
        }
        if(a[0] + a[1] == nr){
            break;
        }
        m--;
    }
    if(p <= m){
        solve(p, m, nrp, a[1]);
        solve(mid + 1, u, a[0] + mid - m, nru);
    }
    else{
        solve(mid + 1, u, nrp + mid - p + 1, nru);
    }
}
int find_best(int n){
    int r, i, p;
    vector<int> a;
    r = sqrt(n * 1.0);
    for(i = 0; i <= r + 100; i++){
        a = ask(i);
        if(a[0] == 0 && a[1] == 0){
            return i;
        }
        if(nr <= a[1] + a[0]){
            nr = a[1] + a[0];
            p = i;
        }
    }
    a = ask(p);
    solve(p, n - 1, a[0], 0);
    return x;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:55:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
     a = ask(p);
         ~~~^~~

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