Submission #715834

#	Time	Username	Problem	Language	Result	Execution time	Memory
715834		bin9638	The Big Prize (IOI17_prize)	C++17	20 / 100	69 ms	412 KiB

prize

#include<bits/stdc++.h>

#ifndef SKY
#include "prize.h"
#endif // SKY

using namespace std;
#define N 200010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>

int n,lolipop;

#ifdef SKY
int p[N];
vector<int> ask(int i)
{
    cout<<"ask "<<i<<endl;
    vector<int>res(2,0);
    for(int j=0;j<i;j++)
        if(p[j]<p[i])
            res[0]++;
    for(int j=i+1;j<n;j++)
        if(p[j]<p[i])
            res[1]++;
    // cout<<i<<endl;
      //  for(int j=0;j<n;j++)cout<<p[j]<<" ";cout<<endl;
      //  cout<<res[0]<<" "<<res[1]<<endl;
    return res;
}
#endif // SKY

int query=0;

vector<int>myAsk(int i)
{
     query++;
    assert(query<=1e4);
    vector<int>res=ask(i);
    return res;
}

vector<int>lis;

void solve(int l,int r)
{
    if(l>r)
        return;
    int mid=(l+r)/2;
    vector<int>s=myAsk(mid);
    if(s[0]+s[1]!=lolipop)
    {
        lis.pb(mid);
        solve(l,mid-1);
        solve(mid+1,r);
        return;
    }
    int lef=0,righ=0;
    while(l<=r)
    {
        vector<int>s=myAsk(l);
        if(s[0]+s[1]!=lolipop)
        {
            lis.pb(l);
            l++;
        }else
        {
            lef=s[0];
            l++;
            break;
        }
    }
    while(r>=l)
    {
        vector<int>s=myAsk(r);
        if(s[0]+s[1]!=lolipop)
        {
            lis.pb(r);
            r--;
        }else
        {
            righ=s[1];
            r--;
            break;
        }
    }
    if(l>r)
        return;
    if(s[0]-lef!=0)
    {
        solve(l,mid-1);
    }
    if(s[1]-righ!=0)
    {
        solve(mid+1,r);
    }
}

int find_best(int cc)
{
    n=cc;
    lis.clear();
    if(n<=7)
    {
        for(int i=0;i<n;i++)
        {
            vector<int>s=myAsk(i);
            if(s[0]==0&&s[1]==0)
                return i;
        }
    }
    lolipop=0;
    for(int i=0;i<sqrt(n)*2;i++)
    {
        vector<int>s=myAsk(i);
        lolipop=max(lolipop,s[0]+s[1]);
    }
    solve(0,n-1);
    for(auto i:lis)
    {
        vector<int>s=myAsk(i);
        if(s[0]==0&&s[1]==0)
            return i;
    }
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i];
    cout<<find_best(n);
    cout<<endl<<query<<endl;
    return 0;
}
#endif // SKY

Compilation message (stderr)

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

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