oj.uz

Submission #715832

# Submission time Handle Problem Language Result Execution time Memory
715832 2023-03-28T07:24:41 Z bin9638 The Big Prize (IOI17_prize) C++17
20 / 100
 79 ms 296 KB 
#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)
{
    assert(i>=0&&i<n);
    vector<int>res=ask(i);
    query++;
    return res;
}

vector<int>lis;

void solve(int l,int r)
{
    if(l>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];
            break;
        }
    }
    while(r>=l)
    {
        vector<int>s=myAsk(r);
        if(s[0]+s[1]!=lolipop)
        {
            lis.pb(r);
            r--;
        }else
        {
            righ=s[1];
            break;
        }
    }
    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;
    }
    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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 9 ms 208 KB Output is correct
3 Correct 13 ms 292 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 10 ms 208 KB Output is correct
6 Correct 10 ms 296 KB Output is correct
7 Correct 11 ms 288 KB Output is correct
8 Correct 9 ms 296 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 10 ms 208 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 10 ms 288 KB Output is correct
3 Correct 10 ms 208 KB Output is correct
4 Correct 6 ms 288 KB Output is correct
5 Correct 7 ms 292 KB Output is correct
6 Correct 10 ms 292 KB Output is correct
7 Correct 10 ms 208 KB Output is correct
8 Correct 8 ms 292 KB Output is correct
9 Correct 8 ms 208 KB Output is correct
10 Correct 8 ms 208 KB Output is correct
11 Correct 23 ms 292 KB Output is correct
12 Correct 21 ms 208 KB Output is correct
13 Correct 9 ms 288 KB Output is correct
14 Correct 24 ms 280 KB Output is correct
15 Incorrect 79 ms 208 KB Incorrect
16 Halted 0 ms 0 KB -