Submission #136139

#	Time	Username	Problem	Language	Result	Execution time	Memory
136139		alexandra_udristoiu	The Big Prize (IOI17_prize)	C++14	100 / 100	61 ms	5308 KiB

prize

#include<iostream>
#include<vector>
#include<cmath>
#include "prize.h"
using namespace std;
static int nr, x;
static vector<int> an[200005];
vector<int> ask2(int p){
    if(an[p].size() == 0){
        an[p] = ask(p);
    }
    return an[p];
}
void solve(int p, int u, int nrp, int nru){
    if(p >= u || nrp + nru == nr){
        return;
    }
    vector<int> a;
    int mid, m;
    mid = (p + u) / 2;
    m = mid + 1;
    while(m <= u){
        a = ask2(m);
        if(a[0] + a[1] == 0){
            x = m;
            return;
        }
        if(a[0] + a[1] == nr){
            break;
        }
        m++;
    }
    if(m <= u){
        solve(p, mid, nrp, a[1] + m - mid - 1);
        solve(m, u, a[0], nru);
    }
    else{
        solve(p, mid, nrp, nru + u - mid);
    }
}
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 = ask2(i);
        if(a[0] == 0 && a[1] == 0){
            return i;
        }
        if(nr <= a[1] + a[0]){
            nr = a[1] + a[0];
            p = i;
        }
        if(nr >= 35){
            break;
        }
    }
    a = ask2(p);
    solve(p, n - 1, a[0], 0);
    return x;
}

Compilation message (stderr)

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

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