oj.uz

Submission #715844

# Submission time Handle Problem Language Result Execution time Memory
715844 2023-03-28T07:44:36 Z bin9638 The Big Prize (IOI17_prize) C++17
20 / 100
 88 ms 640 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,int left_child,int right_child)
{
    if(l>r)
        return;
    int mid=(l+r)/2,v=mid,u=mid-1;
    while(1)
    {
        vector<int>s;
        if(u>=l)
        {
            s=myAsk(u);
            if(s[0]+s[1]!=lolipop)
            {
                lis.pb(u);
                u--;
            }else
            {
                if(s[0]-left_child!=0)
                {
                    solve(l,u-1,left_child,s[1]);
                }
                if(s[1]-right_child!=0)
                {
                    solve(v,r,s[0],right_child);
                }
                return;
            }
        }
        if(v<=r)
        {
            s=myAsk(v);
            if(s[0]+s[1]!=lolipop)
            {
                lis.pb(v);
                v++;
            }else
            {
                if(s[0]-left_child!=0)
                {
                    solve(l,u,left_child,s[1]);
                }
                if(s[1]-right_child!=0)
                {
                    solve(v+1,r,s[0],right_child);
                }
                return;
            }
        }
        if(u<l&&v>r)
            return;
    }
   /* for(int i=mid;i<=r;i++)
    {
        vector<int>s=myAsk(i);
        if(s[0]+s[1]!=lolipop)
        {
            lis.pb(i);
        }else
        {
            if(s[0]-left_child!=0)
            {
                solve(l,mid-1,left_child,s[1]);
            }
            if(s[1]-right_child!=0)
            {
                solve(i+1,r,s[0],right_child);
            }
            return;
        }
    }
    for(int i=mid-1;i>=l;i--)
    {
        vector<int>s=myAsk(i);
        if(s[0]+s[1]!=lolipop)
        {
            lis.pb(i);
        }else
        {
            if(s[0]-left_child!=0)
            {
                solve(l,i-1,left_child,s[1]);
            }
        }
    }*/
}

int find_best(int cc)
{
    n=cc;
    lis.clear();
    if(n<=500)
    {
        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)+10;i++)
    {
        vector<int>s=myAsk(i);
        lolipop=max(lolipop,s[0]+s[1]);
    }
    solve(0,n-1,0,0);
    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:161:1: warning: control reaches end of non-void function [-Wreturn-type]
  161 | }
      | ^

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 5 ms 292 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 3 ms 292 KB Output is correct
7 Correct 5 ms 292 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 3 ms 208 KB Output is correct
10 Correct 4 ms 208 KB Output is correct
11 Correct 11 ms 208 KB Output is correct
12 Correct 7 ms 284 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 13 ms 208 KB Output is correct
15 Partially correct 52 ms 288 KB Partially correct - number of queries: 5359
16 Partially correct 62 ms 296 KB Partially correct - number of queries: 5944
17 Partially correct 44 ms 292 KB Partially correct - number of queries: 5558
18 Partially correct 64 ms 280 KB Partially correct - number of queries: 6007
19 Partially correct 53 ms 208 KB Partially correct - number of queries: 5282
20 Correct 25 ms 280 KB Output is correct
21 Partially correct 49 ms 288 KB Partially correct - number of queries: 5715
22 Correct 23 ms 296 KB Output is correct
23 Correct 3 ms 296 KB Output is correct
24 Correct 7 ms 292 KB Output is correct
25 Partially correct 39 ms 292 KB Partially correct - number of queries: 5469
26 Partially correct 32 ms 336 KB Partially correct - number of queries: 5418
27 Correct 4 ms 336 KB Output is correct
28 Partially correct 41 ms 208 KB Partially correct - number of queries: 5540
29 Correct 18 ms 292 KB Output is correct
30 Partially correct 50 ms 208 KB Partially correct - number of queries: 6000
31 Partially correct 48 ms 292 KB Partially correct - number of queries: 5560
32 Correct 9 ms 288 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 44 ms 280 KB Partially correct - number of queries: 5728
35 Correct 3 ms 208 KB Output is correct
36 Partially correct 59 ms 296 KB Partially correct - number of queries: 5617
37 Correct 9 ms 208 KB Output is correct
38 Correct 6 ms 208 KB Output is correct
39 Partially correct 44 ms 280 KB Partially correct - number of queries: 5731
40 Partially correct 46 ms 208 KB Partially correct - number of queries: 5276
41 Partially correct 47 ms 292 KB Partially correct - number of queries: 5858
42 Partially correct 58 ms 208 KB Partially correct - number of queries: 5858
43 Partially correct 54 ms 292 KB Partially correct - number of queries: 5672
44 Partially correct 44 ms 280 KB Partially correct - number of queries: 5727
45 Partially correct 20 ms 292 KB Partially correct - number of queries: 5298
46 Partially correct 50 ms 208 KB Partially correct - number of queries: 5592
47 Partially correct 43 ms 288 KB Partially correct - number of queries: 5410
48 Partially correct 62 ms 296 KB Partially correct - number of queries: 5951
49 Partially correct 43 ms 296 KB Partially correct - number of queries: 5608
50 Partially correct 62 ms 208 KB Partially correct - number of queries: 6043
51 Partially correct 47 ms 292 KB Partially correct - number of queries: 5736
52 Partially correct 39 ms 208 KB Partially correct - number of queries: 5553
53 Correct 3 ms 292 KB Output is correct
54 Partially correct 51 ms 208 KB Partially correct - number of queries: 5710
55 Partially correct 41 ms 208 KB Partially correct - number of queries: 5581
56 Partially correct 32 ms 292 KB Partially correct - number of queries: 6051
57 Partially correct 52 ms 208 KB Partially correct - number of queries: 5879
58 Partially correct 51 ms 272 KB Partially correct - number of queries: 5851
59 Partially correct 48 ms 292 KB Partially correct - number of queries: 5845
60 Partially correct 40 ms 292 KB Partially correct - number of queries: 5835
61 Correct 6 ms 208 KB Output is correct
62 Correct 5 ms 208 KB Output is correct
63 Correct 4 ms 208 KB Output is correct
64 Correct 5 ms 208 KB Output is correct
65 Correct 5 ms 296 KB Output is correct
66 Correct 11 ms 208 KB Output is correct
67 Correct 11 ms 292 KB Output is correct
68 Correct 9 ms 208 KB Output is correct
69 Correct 8 ms 292 KB Output is correct
70 Correct 4 ms 300 KB Output is correct
71 Partially correct 50 ms 208 KB Partially correct - number of queries: 6633
72 Correct 8 ms 208 KB Output is correct
73 Partially correct 28 ms 300 KB Partially correct - number of queries: 6549
74 Partially correct 44 ms 208 KB Partially correct - number of queries: 6585
75 Correct 6 ms 296 KB Output is correct
76 Partially correct 23 ms 280 KB Partially correct - number of queries: 5769
77 Partially correct 68 ms 208 KB Partially correct - number of queries: 6429
78 Correct 11 ms 208 KB Output is correct
79 Correct 34 ms 280 KB Output is correct
80 Partially correct 28 ms 344 KB Partially correct - number of queries: 6437
81 Partially correct 61 ms 208 KB Partially correct - number of queries: 6447
82 Partially correct 55 ms 280 KB Partially correct - number of queries: 6390
83 Correct 7 ms 208 KB Output is correct
84 Partially correct 41 ms 208 KB Partially correct - number of queries: 5428
85 Partially correct 38 ms 276 KB Partially correct - number of queries: 6418
86 Runtime error 88 ms 640 KB Execution killed with signal 6
87 Halted 0 ms 0 KB -