답안 #715845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715845	2023-03-28T07:46:05 Z	bin9638	커다란 상품 (IOI17_prize)	C++17	90 / 100	93 ms	312 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<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)*2;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

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

Subtask #2

70.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	296 KB	Output is correct
2	Correct	7 ms	208 KB	Output is correct
3	Correct	14 ms	272 KB	Output is correct
4	Correct	9 ms	296 KB	Output is correct
5	Correct	15 ms	208 KB	Output is correct
6	Correct	9 ms	208 KB	Output is correct
7	Correct	16 ms	288 KB	Output is correct
8	Correct	9 ms	208 KB	Output is correct
9	Correct	9 ms	208 KB	Output is correct
10	Correct	9 ms	208 KB	Output is correct
11	Correct	12 ms	208 KB	Output is correct
12	Correct	10 ms	292 KB	Output is correct
13	Correct	13 ms	272 KB	Output is correct
14	Correct	17 ms	280 KB	Output is correct
15	Partially correct	35 ms	276 KB	Partially correct - number of queries: 5796
16	Partially correct	50 ms	272 KB	Partially correct - number of queries: 6381
17	Partially correct	60 ms	276 KB	Partially correct - number of queries: 5995
18	Partially correct	40 ms	276 KB	Partially correct - number of queries: 6444
19	Partially correct	60 ms	280 KB	Partially correct - number of queries: 5719
20	Correct	24 ms	208 KB	Output is correct
21	Partially correct	45 ms	292 KB	Partially correct - number of queries: 6152
22	Correct	46 ms	284 KB	Output is correct
23	Correct	7 ms	296 KB	Output is correct
24	Correct	11 ms	292 KB	Output is correct
25	Partially correct	35 ms	208 KB	Partially correct - number of queries: 5906
26	Partially correct	74 ms	208 KB	Partially correct - number of queries: 5855
27	Correct	10 ms	208 KB	Output is correct
28	Partially correct	64 ms	272 KB	Partially correct - number of queries: 5977
29	Partially correct	40 ms	272 KB	Partially correct - number of queries: 5149
30	Partially correct	66 ms	268 KB	Partially correct - number of queries: 6437
31	Partially correct	68 ms	268 KB	Partially correct - number of queries: 5997
32	Correct	15 ms	292 KB	Output is correct
33	Correct	1 ms	208 KB	Output is correct
34	Partially correct	87 ms	288 KB	Partially correct - number of queries: 6165
35	Correct	13 ms	288 KB	Output is correct
36	Partially correct	63 ms	208 KB	Partially correct - number of queries: 6054
37	Correct	19 ms	288 KB	Output is correct
38	Correct	12 ms	292 KB	Output is correct
39	Partially correct	62 ms	280 KB	Partially correct - number of queries: 6168
40	Partially correct	27 ms	296 KB	Partially correct - number of queries: 5713
41	Partially correct	59 ms	292 KB	Partially correct - number of queries: 6295
42	Partially correct	43 ms	284 KB	Partially correct - number of queries: 6295
43	Partially correct	44 ms	284 KB	Partially correct - number of queries: 6109
44	Partially correct	76 ms	296 KB	Partially correct - number of queries: 6164
45	Partially correct	47 ms	284 KB	Partially correct - number of queries: 5735
46	Partially correct	52 ms	292 KB	Partially correct - number of queries: 6029
47	Partially correct	49 ms	292 KB	Partially correct - number of queries: 5847
48	Partially correct	59 ms	208 KB	Partially correct - number of queries: 6388
49	Partially correct	48 ms	292 KB	Partially correct - number of queries: 6045
50	Partially correct	68 ms	292 KB	Partially correct - number of queries: 6480
51	Partially correct	23 ms	280 KB	Partially correct - number of queries: 6173
52	Partially correct	57 ms	280 KB	Partially correct - number of queries: 5990
53	Correct	8 ms	288 KB	Output is correct
54	Partially correct	56 ms	292 KB	Partially correct - number of queries: 6147
55	Partially correct	49 ms	288 KB	Partially correct - number of queries: 6018
56	Partially correct	48 ms	208 KB	Partially correct - number of queries: 6488
57	Partially correct	52 ms	292 KB	Partially correct - number of queries: 6316
58	Partially correct	60 ms	208 KB	Partially correct - number of queries: 6288
59	Partially correct	47 ms	268 KB	Partially correct - number of queries: 6282
60	Partially correct	61 ms	208 KB	Partially correct - number of queries: 6272
61	Correct	7 ms	300 KB	Output is correct
62	Correct	10 ms	208 KB	Output is correct
63	Correct	10 ms	208 KB	Output is correct
64	Correct	10 ms	292 KB	Output is correct
65	Correct	9 ms	288 KB	Output is correct
66	Correct	11 ms	208 KB	Output is correct
67	Correct	11 ms	276 KB	Output is correct
68	Correct	12 ms	208 KB	Output is correct
69	Correct	12 ms	208 KB	Output is correct
70	Correct	11 ms	296 KB	Output is correct
71	Partially correct	93 ms	276 KB	Partially correct - number of queries: 7069
72	Correct	10 ms	208 KB	Output is correct
73	Partially correct	65 ms	288 KB	Partially correct - number of queries: 6985
74	Partially correct	71 ms	276 KB	Partially correct - number of queries: 7021
75	Correct	6 ms	208 KB	Output is correct
76	Partially correct	59 ms	288 KB	Partially correct - number of queries: 6205
77	Partially correct	50 ms	208 KB	Partially correct - number of queries: 6862
78	Correct	11 ms	208 KB	Output is correct
79	Correct	32 ms	292 KB	Output is correct
80	Partially correct	62 ms	280 KB	Partially correct - number of queries: 6904
81	Partially correct	55 ms	208 KB	Partially correct - number of queries: 6886
82	Partially correct	60 ms	208 KB	Partially correct - number of queries: 6817
83	Correct	11 ms	208 KB	Output is correct
84	Partially correct	49 ms	300 KB	Partially correct - number of queries: 5874
85	Partially correct	68 ms	312 KB	Partially correct - number of queries: 6884
86	Correct	16 ms	208 KB	Output is correct
87	Correct	10 ms	208 KB	Output is correct
88	Correct	17 ms	288 KB	Output is correct
89	Correct	29 ms	208 KB	Output is correct
90	Correct	8 ms	208 KB	Output is correct
91	Correct	11 ms	296 KB	Output is correct
92	Correct	21 ms	208 KB	Output is correct
93	Correct	26 ms	276 KB	Output is correct
94	Correct	12 ms	296 KB	Output is correct
95	Correct	19 ms	208 KB	Output is correct
96	Correct	20 ms	300 KB	Output is correct
97	Correct	16 ms	296 KB	Output is correct