Submission #425433

#	Time	Username	Problem	Language	Result	Execution time	Memory
425433		jk410	The Big Prize (IOI17_prize)	C++17	0 / 100	140 ms	5468 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef vector<int> vi;
int N,RT,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]>N/2&&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]>N/2){
            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=n;
    RT=sqrt(N);
    for (int i=0; i<N; i+=RT){
        find_not_candy(i,min(N-1,i+RT-1));
        if (Ans!=-1)
            return Ans;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^
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: 0 / 20
• Subtask 2: 0 / 80