Submission #226595

#	Time	Username	Problem	Language	Result	Execution time	Memory
226595		CaroLinda	Hiring (IOI09_hiring)	C++14	58 / 100	789 ms	42020 KiB

hiring

#include <bits/stdc++.h>

#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAXN = 5e5+10 ;

using namespace std ;

struct Seg
{

    int s[MAXN*4] ;
    ll v[MAXN*4] ;

    Seg() { memset(v, 0, sizeof v) ; memset(s,0,sizeof s) ; }

    int m(int l, int r) { return (l+r)>>1 ; }

    void upd(int pos, int l, int r, int idx, ll val )
    {
        v[pos] += val ;
        s[pos] ++ ;

        if( l == r ) return ;

        if( idx <= m(l,r) ) upd(pos<<1,l,m(l,r),idx,val) ;
        else upd( (pos<<1)|1 , m(l,r)+1, r, idx, val ) ;

    }

    int bb(int pos, int l, int r, ll soma )
    {

        if( l == r && v[pos] > soma ) return 0 ;
        else if( l == r && v[pos] <= soma ) return 1 ;

        if( v[pos<<1] <= soma ) return s[pos<<1] + bb( (pos<<1)|1 , m(l,r)+1, r, soma - v[pos<<1] ) ;
        return bb(pos<<1,l,m(l,r) , soma) ;

    }

};

int N ;
int S[MAXN] , Q[MAXN] , vet[MAXN] ;
int idx[MAXN] , compressao[MAXN] ;
int resp[MAXN] ;
ll cur_soma ;
vector<int> ans ;
vector<pii> v ;
ll W ;
Seg seg ;


bool cmp(int i, int j)
{
    int val1 = S[i] * Q[j] ;
    int val2 = S[j] * Q[i] ;

    if( val1 != val2 ) return val1 < val2 ;
    return Q[i] <= Q[j] ;
}

bool cmp2(int i , int j)
{
    if( Q[i] == Q[j] ) return S[i] <= S[j] ;
    return Q[i] < Q[j] ;
}

int main()
{
    scanf("%d %lld", &N , &W ) ;
    lp(i,1,N+1) scanf("%d %d", &S[i] , &Q[i]) ;

    lp(i,1,N+1) vet[i] = idx[i] = i ;

    sort(vet+1, vet+1+N,cmp) ;
    sort(idx+1, idx+1+N, cmp2 ) ;

    lp(i,1,N+1) compressao[ idx[i] ] = i ;

    lp(i,1,N+1)
    {

        seg.upd( 1 , 1 , N , compressao[ vet[i] ] , Q[ vet[i] ] ) ;

        ll procuro = ( W * Q[ vet[i] ] )/S[ vet[i] ] ;

        resp[i] = seg.bb( 1 , 1 , N , procuro ) ;

    }

    int great , mx = *max_element( resp+1, resp+1+N ) ;
    lp(i,1,N+1) if( resp[i] == mx ) { great = i ; break ; }

    lp(i,1,great) v.pb( mk( Q[ vet[i] ] , vet[i] ) ) ;
    sort( all(v) ) ;
    lp(i,0,mx-1) ans.pb( v[i].ss ) ;
    ans.pb( vet[great] ) ;

    sort(all(ans)) ;
    printf("%lu\n" , ans.size() ) ;
    for(int i : ans ) printf("%d\n" , i ) ;

}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &N , &W ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
hiring.cpp:82:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     lp(i,1,N+1) scanf("%d %d", &S[i] , &Q[i]) ;
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:102:9: warning: 'great' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int great , mx = *max_element( resp+1, resp+1+N ) ;
         ^~~~~

• Subtask 1: 17 / 30
• Subtask 2: 20 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 3 / 6
• Subtask 8: 3 / 6
• Subtask 9: 3 / 6