oj.uz

답안 #1021633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1021633 2024-07-12T22:35:26 Z vjudge1 Archery (IOI09_archery) C++17
0 / 100
 232 ms 23808 KB 
#include<bits/stdc++.h>
#define N 1<<19
#pragma GCC optimize(2)
typedef long long ll;
#define int ll
using namespace std;
struct fenwick_tree{
    ll T[N]{};
    void upd(int x,int p){
        while(x<N)
            T[x]+=p,x+=x&-x;
    }
    ll qr(int x){
        int ans=0;
        while(x)
            ans+=T[x],x-=x&-x;
        return ans;
    }
} X,cnt;
int h,g,p[N],CC,CC2;
pair<ll,ll>b;
void stuff(ll x,int i,ll A,ll B){
    int l=0,r=5e5,res=0;
    while(l<=r){
        int mid=l+r>>1;
        if(X.qr(mid)<=x)
            l=mid+1,res=mid;
        else r=mid-1;
    }
    ll K=cnt.qr(res),C=X.qr(res);
    if(K>h||K==h&&b.first*B>b.second*A*C)
        h=K,b={A*C,B},g=i;
}
#undef int
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    set<pair<int,int>>st;
    vector<tuple<int,int,int>>v;
    int n;
    ll w;
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        int q,s;
        cin>>s>>q;
        st.insert({q,i});
        v.push_back({q,s,i});
    }
    for(auto[q,i]:st)
        p[i]=++CC;
    sort(v.begin(),v.end(),[](auto a,auto b){
        return get<1>(a)*get<0>(b)<get<0>(a)*get<1>(b);
    });
    for(auto[q,s,i]:v){
        X.upd(p[i],q);
        cnt.upd(p[i],1);
        stuff(w*q/s,++CC2,s,q);
    }
    vector<pair<int,int>>v2;
    for(int i=0;i<g;i++)
        v2.push_back({get<0>(v[i]),get<2>(v[i])});
    sort(v2.begin(),v2.end());
    cout<<h<<'\n';
    for(int i=0;i<h;i++)
        cout<<v2[i].second<<'\n';
}

Compilation message

archery.cpp: In function 'void stuff(ll, ll, ll, ll)':
archery.cpp:25:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int mid=l+r>>1;
      |                 ~^~
archery.cpp:31:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |     if(K>h||K==h&&b.first*B>b.second*A*C)
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 2 ms 604 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 3 ms 860 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct

Subtask #2
0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 2 ms 604 KB Output isn't correct
4 Incorrect 10 ms 1884 KB Output isn't correct
5 Incorrect 162 ms 19944 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Incorrect 12 ms 2140 KB Output isn't correct
9 Incorrect 15 ms 2456 KB Output isn't correct
10 Incorrect 1 ms 600 KB Output isn't correct
11 Incorrect 15 ms 2452 KB Output isn't correct
12 Incorrect 2 ms 604 KB Output isn't correct
13 Incorrect 114 ms 14892 KB Output isn't correct
14 Incorrect 3 ms 856 KB Output isn't correct
15 Incorrect 25 ms 4064 KB Output isn't correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Incorrect 2 ms 600 KB Output isn't correct
18 Incorrect 2 ms 604 KB Output isn't correct
19 Incorrect 2 ms 860 KB Output isn't correct
20 Incorrect 5 ms 1076 KB Output isn't correct
21 Incorrect 14 ms 2388 KB Output isn't correct
22 Incorrect 22 ms 3736 KB Output isn't correct
23 Incorrect 163 ms 21244 KB Output isn't correct
24 Incorrect 1 ms 604 KB Output isn't correct
25 Incorrect 1 ms 644 KB Output isn't correct
26 Incorrect 4 ms 856 KB Output isn't correct
27 Incorrect 14 ms 2456 KB Output isn't correct
28 Incorrect 107 ms 14380 KB Output isn't correct
29 Incorrect 2 ms 604 KB Output isn't correct
30 Incorrect 3 ms 856 KB Output isn't correct
31 Incorrect 13 ms 2196 KB Output isn't correct
32 Incorrect 166 ms 21376 KB Output isn't correct
33 Incorrect 1 ms 348 KB Output isn't correct
34 Incorrect 1 ms 348 KB Output isn't correct
35 Incorrect 2 ms 604 KB Output isn't correct
36 Incorrect 2 ms 604 KB Output isn't correct
37 Incorrect 11 ms 1944 KB Output isn't correct
38 Incorrect 18 ms 3140 KB Output isn't correct
39 Incorrect 1 ms 348 KB Output isn't correct
40 Incorrect 1 ms 604 KB Output isn't correct
41 Incorrect 2 ms 776 KB Output isn't correct
42 Incorrect 2 ms 856 KB Output isn't correct
43 Incorrect 4 ms 860 KB Output isn't correct
44 Incorrect 8 ms 1500 KB Output isn't correct
45 Incorrect 15 ms 2264 KB Output isn't correct
46 Incorrect 15 ms 2456 KB Output isn't correct
47 Incorrect 232 ms 23808 KB Output isn't correct