oj.uz

답안 #715834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715834 2023-03-28T07:27:17 Z bin9638 커다란 상품 (IOI17_prize) C++17
20 / 100
 69 ms 412 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)
{
     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

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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 208 KB Output is correct
2 Correct 7 ms 292 KB Output is correct
3 Correct 9 ms 292 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 5 ms 296 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 8 ms 208 KB Output is correct
8 Correct 8 ms 208 KB Output is correct
9 Correct 8 ms 208 KB Output is correct
10 Correct 9 ms 208 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 10 ms 208 KB Output is correct
3 Correct 4 ms 292 KB Output is correct
4 Correct 8 ms 292 KB Output is correct
5 Correct 9 ms 292 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 7 ms 208 KB Output is correct
8 Correct 5 ms 296 KB Output is correct
9 Correct 9 ms 288 KB Output is correct
10 Correct 10 ms 208 KB Output is correct
11 Correct 9 ms 288 KB Output is correct
12 Correct 22 ms 296 KB Output is correct
13 Correct 22 ms 208 KB Output is correct
14 Correct 19 ms 216 KB Output is correct
15 Runtime error 69 ms 412 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -