Submission #226593

#	Time	Username	Problem	Language	Result	Execution time	Memory
226593		CaroLinda	Hiring (IOI09_hiring)	C++14	45 / 100	1595 ms	17904 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 ;

int N ;
int S[MAXN] , Q[MAXN] , vet[MAXN] ;
ll cur_soma ;
set<pii> s ;
ll W ;
vector<int> ans ;

inline void add(int x, int id) { s.insert( mk(x,id) ) ; cur_soma += 1LL*x ; }
inline void _erase(int x, int id) { s.erase( s.find(mk(x,id)) ) ; cur_soma -= 1LL*x ; }

bool test(int val, bool ok = false)
{

    if( val == 0 ) return true ;

    s.clear() ;
    cur_soma = 0 ;

   // debug("Testando %d\n" , val ) ;

    for(int i = 1 ; i < val ; i++ )  add( Q[ vet[i] ] , vet[i] ) ;

    for(int i = val ; i <= N ; i++ )
    {

        if( (cur_soma+1LL*Q[ vet[i] ])*1LL*S[ vet[i] ] <= W * 1LL*Q[ vet[i] ] )
        {
            if( ok )
            {
                for(auto p : s) ans.pb( p.ss ) ;
                ans.pb( vet[i] ) ;
            }

            return true ;

        }

        add( Q[ vet[i] ] , vet[i] ) ;
        pii p = *(prev(s.end())  ) ;
        _erase( p.ff , p.ss ) ;

    }

    return false ;

}

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] ;
}

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

    iota(vet+1, vet+1+N, 1 ) ;
    sort(vet+1, vet+1+N,cmp) ;

    int l = 0 , r = N , mid , best = 0;

    while( l <= r )
    {
        mid = (l+r)>>1 ;

        if( test(mid) ) { best = mid ; l = mid + 1 ; }
        else r = mid - 1 ;

    }

    test(best, true) ;

    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:76: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:77: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: 19 / 30
• Subtask 2: 14 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6