Submission #226604

#	Time	Username	Problem	Language	Result	Execution time	Memory
226604		CaroLinda	Hiring (IOI09_hiring)	C++14	100 / 100	809 ms	45916 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) || s[pos] == 0 ) return 0 ;
        else if( l == r && v[pos] <= soma )
        {
            soma -= v[pos] ;
            return 1 ;
        }

        if( v[pos<<1] <= soma )
        {
            soma -= v[pos<<1] ;
            return s[pos<<1] + bb( (pos<<1)|1 , m(l,r)+1, r, soma ) ;
        }
        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 soma[MAXN] ;
vector<int> ans ;
vector<pii> v ;
set<pii> s ;
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] ;
}

bool cmp3(int i, int j) { return soma[i] * S[ vet[i] ] * Q[ vet[j] ] >= soma[j] * S[ vet[j] ] * Q[ vet[i] ] ; }

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)
    {

        soma[i] = ( W*1LL*Q[ vet[i] ] )/(1LL*S[ vet[i] ]) ;
        soma[i] -= Q[ vet[i] ] ;
        resp[i] = seg.bb( 1 , 1 , N , soma[i] ) + 1 ;
        seg.upd( 1 , 1 , N , compressao[ vet[i] ] , Q[ vet[i] ] ) ;

    }

    int mx = *max_element( resp+1, resp+1+N ) ;
    vector<int> v ;

    lp(i,1,N+1)
        if( resp[i] == mx ) v.pb( i ) ;

    sort(all(v) , cmp3 ) ;

    int great = v[0] ;

    vector<pii> aux ;

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

    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:92: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:93: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]) ;
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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