Submission #715851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
715851	2023-03-28T07:50:06 Z	bin9638	The Big Prize (IOI17_prize)	C++17	90 / 100	76 ms	404 KB

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<ii>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,s[0]+s[1]});
                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,s[0]+s[1]});
                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)+100;i++)
    {
        vector<int>s=myAsk(i);
        lolipop=max(lolipop,s[0]+s[1]);
    }
    solve(0,n-1,0,0);
    for(auto i:lis)
    {
        if(i.sc==0)
            return i.fs;
    }
}

#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:160:1: warning: control reaches end of non-void function [-Wreturn-type]
  160 | }
      | ^

Subtask #1

20.0 / 20.0

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

Subtask #2

70.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	292 KB	Output is correct
2	Correct	6 ms	288 KB	Output is correct
3	Correct	6 ms	292 KB	Output is correct
4	Correct	5 ms	208 KB	Output is correct
5	Correct	3 ms	336 KB	Output is correct
6	Correct	4 ms	292 KB	Output is correct
7	Correct	4 ms	296 KB	Output is correct
8	Correct	2 ms	296 KB	Output is correct
9	Correct	5 ms	344 KB	Output is correct
10	Correct	4 ms	208 KB	Output is correct
11	Correct	11 ms	208 KB	Output is correct
12	Correct	8 ms	296 KB	Output is correct
13	Correct	11 ms	292 KB	Output is correct
14	Correct	15 ms	300 KB	Output is correct
15	Partially correct	40 ms	288 KB	Partially correct - number of queries: 5383
16	Partially correct	76 ms	280 KB	Partially correct - number of queries: 5643
17	Partially correct	23 ms	300 KB	Partially correct - number of queries: 5647
18	Partially correct	49 ms	280 KB	Partially correct - number of queries: 5625
19	Partially correct	27 ms	292 KB	Partially correct - number of queries: 5371
20	Correct	19 ms	336 KB	Output is correct
21	Partially correct	42 ms	296 KB	Partially correct - number of queries: 5633
22	Correct	41 ms	288 KB	Output is correct
23	Correct	9 ms	296 KB	Output is correct
24	Correct	5 ms	296 KB	Output is correct
25	Partially correct	50 ms	328 KB	Partially correct - number of queries: 5304
26	Partially correct	31 ms	208 KB	Partially correct - number of queries: 5255
27	Correct	7 ms	292 KB	Output is correct
28	Partially correct	45 ms	208 KB	Partially correct - number of queries: 5184
29	Correct	31 ms	292 KB	Output is correct
30	Partially correct	47 ms	296 KB	Partially correct - number of queries: 5622
31	Partially correct	46 ms	284 KB	Partially correct - number of queries: 5649
32	Correct	8 ms	288 KB	Output is correct
33	Correct	0 ms	208 KB	Output is correct
34	Partially correct	53 ms	396 KB	Partially correct - number of queries: 5674
35	Correct	5 ms	288 KB	Output is correct
36	Partially correct	54 ms	280 KB	Partially correct - number of queries: 5603
37	Correct	5 ms	280 KB	Output is correct
38	Correct	8 ms	208 KB	Output is correct
39	Partially correct	49 ms	208 KB	Partially correct - number of queries: 5614
40	Correct	49 ms	288 KB	Output is correct
41	Partially correct	50 ms	280 KB	Partially correct - number of queries: 5679
42	Partially correct	63 ms	288 KB	Partially correct - number of queries: 5679
43	Partially correct	48 ms	292 KB	Partially correct - number of queries: 5520
44	Partially correct	46 ms	288 KB	Partially correct - number of queries: 5634
45	Partially correct	59 ms	404 KB	Partially correct - number of queries: 5239
46	Partially correct	37 ms	280 KB	Partially correct - number of queries: 5681
47	Partially correct	47 ms	288 KB	Partially correct - number of queries: 5283
48	Partially correct	57 ms	288 KB	Partially correct - number of queries: 5705
49	Partially correct	56 ms	208 KB	Partially correct - number of queries: 5664
50	Partially correct	31 ms	284 KB	Partially correct - number of queries: 5661
51	Partially correct	48 ms	336 KB	Partially correct - number of queries: 5641
52	Partially correct	40 ms	280 KB	Partially correct - number of queries: 5639
53	Correct	3 ms	336 KB	Output is correct
54	Partially correct	49 ms	288 KB	Partially correct - number of queries: 5607
55	Partially correct	55 ms	292 KB	Partially correct - number of queries: 5670
56	Partially correct	41 ms	288 KB	Partially correct - number of queries: 5669
57	Partially correct	76 ms	296 KB	Partially correct - number of queries: 5638
58	Partially correct	49 ms	280 KB	Partially correct - number of queries: 5604
59	Partially correct	47 ms	284 KB	Partially correct - number of queries: 5666
60	Partially correct	37 ms	208 KB	Partially correct - number of queries: 5676
61	Correct	5 ms	292 KB	Output is correct
62	Correct	7 ms	208 KB	Output is correct
63	Correct	9 ms	292 KB	Output is correct
64	Correct	11 ms	292 KB	Output is correct
65	Correct	6 ms	208 KB	Output is correct
66	Correct	8 ms	276 KB	Output is correct
67	Correct	7 ms	208 KB	Output is correct
68	Correct	8 ms	288 KB	Output is correct
69	Correct	9 ms	280 KB	Output is correct
70	Correct	9 ms	300 KB	Output is correct
71	Partially correct	52 ms	288 KB	Partially correct - number of queries: 6250
72	Correct	9 ms	208 KB	Output is correct
73	Partially correct	64 ms	300 KB	Partially correct - number of queries: 6173
74	Partially correct	45 ms	208 KB	Partially correct - number of queries: 6206
75	Correct	8 ms	208 KB	Output is correct
76	Partially correct	64 ms	296 KB	Partially correct - number of queries: 5458
77	Partially correct	57 ms	208 KB	Partially correct - number of queries: 6040
78	Correct	11 ms	208 KB	Output is correct
79	Correct	27 ms	208 KB	Output is correct
80	Partially correct	42 ms	300 KB	Partially correct - number of queries: 6052
81	Partially correct	49 ms	208 KB	Partially correct - number of queries: 6073
82	Partially correct	64 ms	280 KB	Partially correct - number of queries: 5986
83	Correct	4 ms	208 KB	Output is correct
84	Partially correct	32 ms	288 KB	Partially correct - number of queries: 5122
85	Partially correct	61 ms	208 KB	Partially correct - number of queries: 6063
86	Correct	9 ms	300 KB	Output is correct
87	Correct	5 ms	208 KB	Output is correct
88	Correct	10 ms	208 KB	Output is correct
89	Correct	8 ms	292 KB	Output is correct
90	Correct	5 ms	208 KB	Output is correct
91	Correct	7 ms	300 KB	Output is correct
92	Correct	15 ms	208 KB	Output is correct
93	Correct	7 ms	296 KB	Output is correct
94	Correct	13 ms	208 KB	Output is correct
95	Correct	15 ms	296 KB	Output is correct
96	Correct	7 ms	300 KB	Output is correct
97	Correct	10 ms	280 KB	Output is correct