oj.uz

답안 #226604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
226604 2020-04-24T13:33:55 Z CaroLinda Hiring (IOI09_hiring) C++14
100 / 100
 809 ms 45916 KB 
#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23936 KB Output is correct
7 Correct 17 ms 23936 KB Output is correct
8 Correct 18 ms 23936 KB Output is correct
9 Correct 19 ms 24064 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 20 ms 24192 KB Output is correct
12 Correct 24 ms 24184 KB Output is correct
13 Correct 22 ms 24184 KB Output is correct
14 Correct 32 ms 24448 KB Output is correct
15 Correct 27 ms 24440 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23936 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 31 ms 24704 KB Output is correct
5 Correct 165 ms 26204 KB Output is correct
6 Correct 345 ms 36452 KB Output is correct
7 Correct 607 ms 41564 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 16 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 16 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 16 ms 23936 KB Output is correct
3 Correct 17 ms 23936 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 28780 KB Output is correct
2 Correct 124 ms 28756 KB Output is correct
3 Correct 140 ms 28844 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 535 ms 32872 KB Output is correct
2 Correct 544 ms 32740 KB Output is correct
3 Correct 519 ms 32740 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 587 ms 43228 KB Output is correct
2 Correct 570 ms 43304 KB Output is correct
3 Correct 577 ms 43356 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 781 ms 45868 KB Output is correct
2 Correct 809 ms 45916 KB Output is correct
3 Correct 762 ms 45916 KB Output is correct