Submission #713061

#	Time	Username	Problem	Language	Result	Execution time	Memory
713061		lam	The Big Prize (IOI17_prize)	C++14	90 / 100	107 ms	1440 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define ff first
#define ss second
const int maxn = 2e5 + 10;
int n;
int ans;
int rt; ii bound;
int f[maxn];
bool dau[maxn];
//vector <int> ask(int x)
//{
//    cout<<x<<endl;
//    int l,r; cin>>l>>r;
//    return {l,r};
//}
void update(int x, int val)
{
    x++;
    while (x<=n)
    {
        f[x]+=val;
        x+=(x&-x);
    }
}
int get(int x)
{
    x++;
    int temp=0;
    while (x>0)
    {
        temp+=f[x];
        x-=(x&-x);
    }
    return temp;
}
int find_best(int N)
{
    n=N;
    int it = min(n,474);
    rt=-1;
    for (int i=0; i<it; i++)
    {
        vector <int> tmp = ask(i);
        int sum = tmp[0] + tmp[1];
        if (sum==0) return i;
        if (rt==-1||bound.ff+bound.ss<sum)
        {
            rt = i;
            bound.ff = tmp[0]; bound.ss = tmp[1];
        }
    }
    fill_n(f,n+1,0);
    for (int i=0; i<bound.ss; i++)
    {
        int l=rt+1; int r=n-1;
        int j = -1;
        int val;
        while (l<=r)
        {
            int mid=(l+r)/2;
            vector <int> tmp = ask(mid);
            if (dau[mid])
            {
                l=mid+1;
                continue;
            }
            if (tmp[0] + tmp[1] != bound.ff + bound.ss || tmp[0] - get(mid) != bound.ff)
            {
                j = mid;
                val = tmp[0] + tmp[1];
                r=mid-1;
            }
            else l=mid+1;
        }
        dau[j]=1;
//        cout<<j<<" :: "<<val<<endl;
        update(j,1);
        if (val==0) return j;
    }
}

//signed main()
//{
//    int n; cin>>n;
//    cout<<find_best(n)<<"!!"<<endl;
//}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^
prize.cpp:82:9: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |         if (val==0) return j;
      |         ^~

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