Submission #425442

#	Time	Username	Problem	Language	Result	Execution time	Memory
425442		jk410	The Big Prize (IOI17_prize)	C++17	100 / 100	73 ms	5188 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef vector<int> vi;
int N,M,Cnt=1,Max,Sum,Ans=-1;
vi ask_res[200000];
vi ask_query(int i){
    vi &r=ask_res[i];
    if (r.size())
        return r;
    return r=ask(i);
}
void find_not_candy(int s,int e){
    if (s>e)
        return;
    vi q=ask_query(e);
    if (q[0]+q[1]==Max&&Sum==q[0])
        return;
    int l=s,r=e,t;
    while (l<=r){
        int m=(l+r)>>1;
        q=ask_query(m);
        if (q[0]+q[1]==Max){
            if (Sum<q[0])
                r=m-1;
            else
                l=m+1;
        }
        else{
            t=m;
            r=m-1;
        }
    }
    q=ask_query(t);
    if (!q[0]&&!q[1]){
        Ans=t;
        return;
    }
    Sum++;
    find_not_candy(t+1,e);
}
int find_best(int n) {
    N=M=n;
    while (M!=1){
        int t=sqrt(M);
        if (t*(t+1)>M)
            t--;
        Cnt+=t;
        M=t;
    }
    for (int i=0; i<N; i+=N/Cnt){
        vi q=ask_query(min(N-1,i+N/Cnt-1));
        Max=max(Max,q[0]+q[1]);
    }
    for (int i=0; i<N; i+=N/Cnt){
        find_not_candy(i,min(N-1,i+N/Cnt-1));
        if (Ans!=-1)
            return Ans;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^
prize.cpp: In function 'void find_not_candy(int, int)':
prize.cpp:40:19: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |     find_not_candy(t+1,e);
      |     ~~~~~~~~~~~~~~^~~~~~~

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