Submission #95258

#	Time	Username	Problem	Language	Result	Execution time	Memory
95258		andy627	The Big Prize (IOI17_prize)	C++17	100 / 100	49 ms	1336 KiB

prize

#include "prize.h"
#include<algorithm>
struct A
{
    int left,right,sum,num;
    bool stop;
}data[200005];
int check[200005];
bool comp(struct A a,struct A b)
{
    if(a.sum<b.sum) return true;
    if(a.sum==b.sum && a.num<b.num) return true;
    return false;
}
bool srt(struct A a,struct A b)
{
    return a.num<b.num;
}
int find_best(int n) {
    int cnt=1,i;
    std::vector<int> a=ask(0);
    data[0].left=a[0];
    data[0].right=a[1];
    data[0].sum=a[0]+a[1];
    check[0]=1;
    if(data[0].sum==0) return 0;
    while(cnt<=n)
    {
        int mid,until=cnt;
        for(i=0;i<until-1;i++)
        {
            mid=(data[i].num+data[i+1].num)/2;
            if(data[i].stop==false && check[mid]==0)
            {
                a=ask(mid);
                data[cnt].left=a[0];
                data[cnt].right=a[1];
                data[cnt].num=mid;
                data[cnt].sum=a[0]+a[1];
                check[mid]=1;
                cnt++;
            }
        }
        mid=(data[i].num+n)/2;
        if(data[i].stop==false && check[mid]==0)
        {
            a=ask(mid);
            data[cnt].left=a[0];
            data[cnt].right=a[1];
            data[cnt].num=mid;
            data[cnt].sum=a[0]+a[1];
            cnt++;
        }
        std::sort(data,data+cnt,comp);
        if(data[0].sum==0) return data[0].num;
        int right_zero=n,left_zero=-1;
        for(i=0;i<cnt-1;i++)
        {
            if(data[i].sum==data[i+1].sum && data[i].right-data[i+1].right==0) data[i].stop=true;
            if(data[i].right==0 && right_zero>data[i].num) right_zero=data[i].num;
            if(data[i].left==0 && left_zero<data[i].num) left_zero=data[i].num;
        }
        if(data[i].right==0 && right_zero>data[i].num) right_zero=data[i].num;
        if(data[i].left==0 && left_zero<data[i].num) left_zero=data[i].num;
        std::sort(data,data+cnt,srt);
        for(i=0;i<cnt;i++)
        {
            if(data[i].num<left_zero) data[i].stop=true;
            if(data[i].num>=right_zero) data[i].stop=true;
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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