답안 #426963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
426963	2021-06-14T11:17:16 Z	A_D	커다란 상품 (IOI17_prize)	C++14	90 / 100	127 ms	8960 KB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;


mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());


const int NN=2e5+100;
vector<int> vec[NN];
int bit[NN];
int seg[4*NN];
vector<int> order;
void build(int p,int s,int e)
{
    if(s==e){
        seg[p]=1;
        return;
    }
    build(p*2,s,(s+e)/2);
    build(p*2+1,(s+e)/2+1,e);
    seg[p]=seg[p*2]+seg[p*2+1];
}
int get3(int p,int s,int e,int tar)
{
    if(s==e){
        return s;
    }
//    cout<<s<<" "<<e<<" "<<tar<<" "<<seg[p*2]<<endl;
    if(seg[p*2]>=tar){
        return get3(p*2,s,(s+e)/2,tar);
    }
    else{
        return get3(p*2+1,(s+e)/2+1,e,tar-seg[p*2]);
    }
}
void update(int p,int s,int e,int i)
{
    if(s==e){
        seg[p]=0;
        return;
    }
    int mid=(s+e)/2;
    if(i<=mid){
        update(p*2,s,mid,i);
    }
    else{
        update(p*2+1,mid+1,e,i);
    }
    seg[p]=seg[p*2]+seg[p*2+1];
}
void add(int idx)
{
    while(idx<NN){
        bit[idx]++;
        idx+=(idx&-idx);
    }
}
int get(int idx)
{
    int ret=0;
    while(idx>0){
        ret+=bit[idx];
        idx-=(idx&-idx);
    }
    return ret;
}
int get(int p,int s,int e,int a,int b)
{
    if(a<=s&&e<=b)return seg[p];
    if(s>b||e<a)return 0;
    return get(p*2,s,(s+e)/2,a,b)+get(p*2+1,(s+e)/2+1,e,a,b);
}
int find_best(int n){
    for(int i=0;i<n;i++)order.push_back(i);
    shuffle(order.begin(),order.end(),rng);
    int cnt=0;
    int mx=0;
    for(auto x:order){
        cnt++;
        vec[x]=ask(x);
        int h=vec[x][0]+vec[x][1];
        mx=max(mx,h);
        if(cnt==1000){
            break;
        }
    }
//    cout<<mx<<endl;
    build(1,0,n-1);
    while(1){
        int l=0,r=n-1;
        while(l<=r){
            int v=0;
            if(l!=0)v+=get(1,0,n-1,0,l-1);
//            cout<<v<<" ";
            v+=(get(1,0,n-1,l,r)+1)/2;
  //          cout<<get(1,0,n-1,l,r)<<" ";
    //        cout<<v<<"\n";
            int mid=get3(1,0,n-1,v);
            if(vec[mid].empty()){
                vec[mid]=ask(mid);
            }
            int h=vec[mid][0]+vec[mid][1];
      //      cout<<l<<" "<<r<<" "<<mid<<" "<<vec[mid][0]<<" "<<vec[mid][1]<<" "<<v<<endl;
            if(h==0)return mid;
            if(h!=mx){
                update(1,0,n-1,mid);
                add(mid+2);
                break;
            }
            if(vec[mid][0]-get(mid+2)){
        //        cout<<"l\n";
                r=mid-1;
            }
            else{
          //      cout<<"r\n";
                l=mid+1;
            }
        }
    }
    assert(0);
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	7920 KB	Output is correct
2	Correct	22 ms	7920 KB	Output is correct
3	Correct	21 ms	7916 KB	Output is correct
4	Correct	17 ms	7980 KB	Output is correct
5	Correct	29 ms	7956 KB	Output is correct
6	Correct	33 ms	7960 KB	Output is correct
7	Correct	27 ms	7916 KB	Output is correct
8	Correct	18 ms	8036 KB	Output is correct
9	Correct	18 ms	7968 KB	Output is correct
10	Correct	27 ms	7836 KB	Output is correct

Subtask #2

70.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	7960 KB	Output is correct
2	Correct	23 ms	7924 KB	Output is correct
3	Correct	30 ms	7856 KB	Output is correct
4	Correct	28 ms	7920 KB	Output is correct
5	Correct	20 ms	7968 KB	Output is correct
6	Correct	20 ms	7924 KB	Output is correct
7	Correct	17 ms	7968 KB	Output is correct
8	Correct	27 ms	7916 KB	Output is correct
9	Correct	17 ms	7972 KB	Output is correct
10	Correct	26 ms	7848 KB	Output is correct
11	Correct	25 ms	8084 KB	Output is correct
12	Correct	32 ms	7948 KB	Output is correct
13	Correct	21 ms	8348 KB	Output is correct
14	Correct	14 ms	5476 KB	Output is correct
15	Correct	34 ms	8048 KB	Output is correct
16	Partially correct	43 ms	8632 KB	Partially correct - number of queries: 5510
17	Correct	22 ms	7984 KB	Output is correct
18	Partially correct	78 ms	8928 KB	Partially correct - number of queries: 6477
19	Correct	27 ms	7920 KB	Output is correct
20	Correct	33 ms	6584 KB	Output is correct
21	Correct	51 ms	8256 KB	Output is correct
22	Correct	23 ms	7960 KB	Output is correct
23	Correct	22 ms	7960 KB	Output is correct
24	Correct	27 ms	7916 KB	Output is correct
25	Correct	35 ms	8360 KB	Output is correct
26	Correct	72 ms	8360 KB	Output is correct
27	Correct	21 ms	7952 KB	Output is correct
28	Partially correct	76 ms	8756 KB	Partially correct - number of queries: 5988
29	Correct	63 ms	8616 KB	Output is correct
30	Partially correct	85 ms	8912 KB	Partially correct - number of queries: 6398
31	Correct	26 ms	7952 KB	Output is correct
32	Correct	24 ms	8228 KB	Output is correct
33	Correct	5 ms	4936 KB	Output is correct
34	Correct	28 ms	8220 KB	Output is correct
35	Correct	22 ms	8072 KB	Output is correct
36	Correct	25 ms	8160 KB	Output is correct
37	Correct	21 ms	8024 KB	Output is correct
38	Correct	19 ms	7972 KB	Output is correct
39	Correct	69 ms	8212 KB	Output is correct
40	Partially correct	56 ms	8780 KB	Partially correct - number of queries: 5644
41	Correct	36 ms	8504 KB	Output is correct
42	Correct	75 ms	8356 KB	Output is correct
43	Correct	53 ms	8300 KB	Output is correct
44	Correct	55 ms	8244 KB	Output is correct
45	Correct	28 ms	8288 KB	Output is correct
46	Correct	22 ms	7952 KB	Output is correct
47	Correct	38 ms	8292 KB	Output is correct
48	Correct	79 ms	8500 KB	Output is correct
49	Correct	33 ms	7928 KB	Output is correct
50	Partially correct	67 ms	8740 KB	Partially correct - number of queries: 6498
51	Correct	63 ms	8200 KB	Output is correct
52	Correct	19 ms	7972 KB	Output is correct
53	Correct	28 ms	7984 KB	Output is correct
54	Correct	63 ms	8212 KB	Output is correct
55	Correct	25 ms	7912 KB	Output is correct
56	Partially correct	97 ms	8884 KB	Partially correct - number of queries: 6493
57	Correct	87 ms	8552 KB	Output is correct
58	Correct	82 ms	8476 KB	Output is correct
59	Correct	52 ms	8304 KB	Output is correct
60	Correct	69 ms	8332 KB	Output is correct
61	Correct	19 ms	7960 KB	Output is correct
62	Correct	27 ms	7956 KB	Output is correct
63	Correct	21 ms	8084 KB	Output is correct
64	Correct	35 ms	7920 KB	Output is correct
65	Correct	32 ms	7988 KB	Output is correct
66	Partially correct	63 ms	7964 KB	Partially correct - number of queries: 5037
67	Correct	23 ms	8052 KB	Output is correct
68	Correct	36 ms	7988 KB	Output is correct
69	Correct	82 ms	7972 KB	Output is correct
70	Correct	36 ms	7864 KB	Output is correct
71	Partially correct	90 ms	8740 KB	Partially correct - number of queries: 7099
72	Correct	35 ms	8368 KB	Output is correct
73	Partially correct	117 ms	8756 KB	Partially correct - number of queries: 7022
74	Partially correct	127 ms	8884 KB	Partially correct - number of queries: 7046
75	Correct	29 ms	7972 KB	Output is correct
76	Partially correct	76 ms	8788 KB	Partially correct - number of queries: 6224
77	Partially correct	110 ms	8696 KB	Partially correct - number of queries: 6547
78	Correct	33 ms	8228 KB	Output is correct
79	Correct	51 ms	8660 KB	Output is correct
80	Partially correct	111 ms	8756 KB	Partially correct - number of queries: 6535
81	Partially correct	78 ms	8808 KB	Partially correct - number of queries: 6563
82	Partially correct	83 ms	8808 KB	Partially correct - number of queries: 6510
83	Correct	28 ms	8040 KB	Output is correct
84	Partially correct	88 ms	8960 KB	Partially correct - number of queries: 5542
85	Partially correct	94 ms	8756 KB	Partially correct - number of queries: 6531
86	Correct	86 ms	8572 KB	Output is correct
87	Correct	34 ms	8116 KB	Output is correct
88	Correct	41 ms	8104 KB	Output is correct
89	Correct	75 ms	8352 KB	Output is correct
90	Correct	23 ms	7952 KB	Output is correct
91	Correct	48 ms	8524 KB	Output is correct
92	Correct	36 ms	7988 KB	Output is correct
93	Partially correct	62 ms	8744 KB	Partially correct - number of queries: 5572
94	Partially correct	82 ms	8732 KB	Partially correct - number of queries: 5795
95	Partially correct	98 ms	8756 KB	Partially correct - number of queries: 5820
96	Partially correct	79 ms	8772 KB	Partially correct - number of queries: 5806
97	Partially correct	71 ms	8780 KB	Partially correct - number of queries: 5152