QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106984 | #862. Social Justice | Sorting | WA | 1ms | 3500kb | C++20 | 2.4kb | 2023-05-20 01:28:38 | 2023-05-20 01:28:42 |
Judging History
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'