QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106984#862. Social JusticeSortingWA 1ms3500kbC++202.4kb2023-05-20 01:28:382023-05-20 01:28:42

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:28:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3500kb
  • [2023-05-20 01:28:38]
  • 提交

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 ;
    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[ i - 1 ].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: 0ms
memory: 3500kb

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: -100
Wrong Answer
time: 1ms
memory: 3448kb

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 
2
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 
0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

10
2 3 4 5 6 8 9 15 16 20 
10
1 5 6 8 12 14 15 16 17 19 
0

0

0

10
1 2 3 4 5 6 10 15 16 20 
0

10
2 3 11 12 13 14 15 17 18 19 
0

0

10
2 5 6 9 10 11 13 ...

result:

wrong answer 11th numbers differ - expected: '3', found: '2'