QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106991#862. Social JusticeSortingAC ✓309ms18988kbC++202.5kb2023-05-20 01:37:592023-05-20 01:38:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 01:38:00]
  • 评测
  • 测评结果:AC
  • 用时:309ms
  • 内存:18988kb
  • [2023-05-20 01:37:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 2e5 + 7 ;

int n ;
pair < ll , ll > a[ MAXN ] ;
ll pref[ MAXN ] ;
ll p , q ;
int add[ MAXN ] ;

bool f ( int len ) {
    for ( int i = 1 ; i + len - 1 <= n ; ++ i ) {
        ll sm = pref[ i + len - 1 ] - pref[ i - 1 ] ;
        ll aux1 = q * len * a[ i + len - 1 ].fi ;
        ll aux2 = p * sm ;
        if ( aux1 <= aux2 ) { return true ; }
    }
    return false ;
}

int bad[ MAXN ] ;

void solve ( ) {
    cin >> n ;
    for ( int i = 0 ; i <= n + 1 ; ++ i ) {
        add[ i ] = 0 ;
        bad[ i ] = 0 ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].fi ;
        a[ i ].se = i ;
    }
    cin >> p >> q ;
    sort ( a + 1 , a + n + 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        pref[ i ] = pref[ i - 1 ] + a[ i ].fi ;
    }
    int l , r , mid ;
    l = 1 , r = n ;
    while ( l < r ) {
        mid = ( l + r + 1 ) / 2 ;
        if ( f ( mid ) == true ) { l = mid ; }
        else { r = mid - 1 ; }
    }
    int len = l ;
    if ( a[ len ].fi * len * q <= pref[ len ] * p ) {
        ++ add[ 1 ] , -- add[ len + 1 ] ;
    }
    for ( int i = 2 ; i + len - 2 <= n ; ++ i ) {
        ll sm = pref[ i + len - 2 ] - pref[ i - 1 ] ;
        ll aux1 = q * len * a[ i + len - 2 ].fi ;
        ll aux2 = p * sm ;
        if ( aux1 > aux2 + p * a[ i - 1 ].fi ) { continue ; }
        l = 1 , r = i - 1 ;
        while ( l < r ) {
            mid = ( l + r ) / 2 ;
            if ( aux1 <= aux2 + p * a[ mid ].fi ) { r = mid ; }
            else { l = mid + 1 ; }
        }
        ++ add[ l ] , -- add[ i ] ;
        ++ add[ i ] , -- add[ i + len - 1 ] ;
    }
    int sm = 0 , cnt = 0 ;
    set < int > s ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        sm = sm + add[ i ] ;
        if ( sm == 0 ) { bad[ a[ i ].se ] = 1 ; ++ cnt ; }
        else { s.insert ( a[ i ].fi ) ; }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( bad[ a[ i ].se ] == 1 && s.find ( a[ i ].fi ) != s.end ( ) ) {
            bad[ a[ i ].se ] = 0 ;
            -- cnt ;
        }
    }
    cout << cnt << "\n" ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( bad[ i ] == 1 ) { cout << i << " " ; }
    }
    cout << "\n" ;
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3368kb

input:

3
4
1 2 3 4
3 2
5
1 15 2 5 1
2 1
5
1 2 3 1000 10000
4 3

output:

0

1
2 
2
4 5 

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 4ms
memory: 3376kb

input:

1000
1
10
3 2
2
10 100
3 2
3
10 10 100
3 2
4
1 2 3 4
3 2
5
1 15 2 5 1
2 1
5
1 2 3 1000 10000
4 3
6
1 2 3 4 1000 10000
4 3
5
50000 2 1 1 5000
2 1
10
1 15 2 5 1 10000 1 1 1 1
2 1
20
1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 10000 1 1 1 1
2 1
25
1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1 10000 1 1 1 1 1 15 2 5 1
2 ...

output:

0

0

1
3 
0

1
2 
2
4 5 
3
1 5 6 
2
1 5 
3
2 4 6 
6
2 4 6 12 14 16 
8
2 4 6 12 14 16 22 24 
13
1 2 3 4 5 6 7 8 9 10 11 12 20 
15
1 2 3 4 5 6 7 8 9 10 11 12 18 19 20 
0

2
2 8 
2
9 12 
2
2 14 
10
1 4 5 6 7 13 14 15 18 20 
2
9 16 
2
16 18 
2
5 13 
10
4 5 6 9 11 15 16 18 19 20 
2
5 19 
2
5 13 
2
10 15...

result:

ok 6086 numbers

Test #3:

score: 0
Accepted
time: 97ms
memory: 4224kb

input:

125
5000
1 1 1 1000000000 1000000000 1000000000 1000000000 1 1 1 1 1 1000000000 1 1 1 1 1 1 1000000000 1000000000 1 1000000000 1000000000 1000000000 1 1000000000 1000000000 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1 1000000000...

output:

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

4491
3 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 39 40 42 43 44 45 46 48 49 50 51 53 54 55 56 57 58 59 62 63 64 66 67 68 70 71 72 74 75 76 77 78 79 80 81 82 83 84 85 87 88 89 90 93 94 95 96 97 ...

result:

ok 242748 numbers

Test #4:

score: 0
Accepted
time: 215ms
memory: 18988kb

input:

5
200000
512314734 33319999 85503340 443544695 92411616 149252701 723302421 176149500 143875507 972078271 907672089 585808794 390600756 700244129 848509047 550288071 859158053 356354007 437419096 572862734 118863313 959486458 472657137 107261032 199102866 190553436 489624108 79203044 147746132 47881...

output:

181062
1 2 3 4 5 6 7 8 9 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 43 44 45 46 47 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 94 95 96 98 99 100 101 102 103 104 105 106 1...

result:

ok 380173 numbers

Test #5:

score: 0
Accepted
time: 309ms
memory: 15332kb

input:

5
200000
15187692 56 41 5053827 3148366 6530 10 131 4381 380972680 499497 8727 371 555036936 2810792 641 3116415 4514225 22284 542730997 129 2227 173361 49408 4 528 1 2660 20568 466863 1 5348 206792 6 150 37 576581 240275683 318 24664 99 34829 38855 177 18018 189646 653 437641 2 219866 5294 3476 856...

output:

83879
2 3 7 8 9 13 16 21 22 25 26 27 28 31 34 35 36 39 41 44 47 49 52 54 58 60 61 66 67 68 69 70 71 72 73 75 77 81 84 86 88 90 92 93 95 96 97 98 99 100 105 106 107 114 117 119 121 122 123 125 126 130 131 135 136 146 147 148 149 152 153 154 156 158 160 161 163 168 170 171 174 179 180 182 184 186 189 ...

result:

ok 176756 numbers