QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#174513#6632. Minimize MedianPERAPROML 320ms5540kbC++202.9kb2023-09-10 08:35:582023-09-10 08:35:58

Judging History

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

  • [2023-09-10 08:35:58]
  • 评测
  • 测评结果:ML
  • 用时:320ms
  • 内存:5540kb
  • [2023-09-10 08:35:58]
  • 提交

answer

/// Write by Daniel Perez .PERAPRO
#include<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(), s.end()
#define mp make_pair
//#define int long long
#define ll long long
// typedef unsigned long long ull;
typedef long double ld;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
#define endl '\n'
char el = '\n';
char esp = ' ';


int cost [1000001] ; 
int cont [1000001] ; 
// bool visit1 [1000001] ; 
bitset<1000001> visit1;
int n , m , c ; 
bool bus ( int h ){
    long long sum1 = 0 ; 
    for ( int i = 0 ; i <= m ; i++ ) visit1 [i] = 0 ;  
    long long cont1 = 0 ; 
    priority_queue < pair < int , int > > q ; 
    for ( int i = 0 ; i <= h ; i++ ){
        q.push ( { 0 , i } ) ;
    }
    while ( !q.empty(  ) ){
        pair < int , int > k = q.top ( ) ;
        q.pop ( ) ;
        if ( visit1 [k.second] ) continue ; 
        visit1 [k.second] = true ;
        for ( int i = 0 ; i < cont[k.second] ; i++ ){
            sum1 += -k.first; 
            cont1++ ; 
            if ( sum1 > c ) return false;
            if ( cont1 == n / 2 + 1 ) return true ; 
        }
        for ( int i = 1 ; i <= m ; i++ ){
            long long p = k.second * i ; 
            long long sum = - ( (- ( k.first)) + cost[i] ) ; 
            if ( p > m ) break ; 
            for ( int d = 0 ; d < i ; d++ ){
                if ( p + d > m ) break ; 
                q.push (  {sum , p + d }) ;               
            }
        }
    }
    return false ; 
}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
ostream& operator<<(ostream& os, const vector<T> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<'\n';
    return os;
}
string yes="YES";
string no="NO";

int32_t main(){
	fast_io;
	/*
 	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    int tc;
    cin>>tc;
    
    while(tc--){

        cin>>n>>m>>c ; 
        for ( int i = 0 ; i <= m ; i++ ) cont [i] = 0 ; 
        for ( int i = 0 ; i < n ; i++ ){
            int a ; 
            cin>>a ;
            cont[a]++ ; 
        }
        for ( int i = 1 ;i <= m ;i++){
            int a ; 
            cin>>a ; 
            cost[i] = a  ; 
        }
        int lo = 0 ;
        int hi = m+1 ; 
        int best = INT_MAX ; 
        while ( lo < hi ){
            int mid = ( lo + hi ) / 2 ;
            if ( bus ( mid ) ){
                best = min ( best , mid ) ; 
                hi = mid  ; 
            }
            else{
                lo = mid + 1 ; 
            }
        }
        cout<<best<<endl ; 
    }

}

/*

*/

詳細信息

Test #1:

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

input:

3
3 5 0
2 5 2
3 2 4 6 13
3 5 3
2 5 3
3 2 4 6 13
3 5 6
2 5 2
3 2 4 6 13

output:

2
2
1

result:

ok 3 number(s): "2 2 1"

Test #2:

score: 0
Accepted
time: 320ms
memory: 5528kb

input:

100000
5 10 5
3 7 1 10 10
11 6 11 6 1 8 9 1 3 1
5 6 51
2 2 2 5 1
42 61 26 59 100 54
5 10 76
7 5 8 4 7
97 4 44 83 61 45 24 88 44 44
5 8 90
1 1 5 1 3
35 15 53 97 71 83 26 7
5 3 52
1 1 3 1 1
22 6 93
5 6 28
6 6 1 3 1
9 31 2 19 10 27
5 8 31
3 6 2 1 2
32 29 13 7 57 34 9 5
5 6 75
3 3 4 5 4
40 56 38 60 17 3...

output:

0
2
0
0
0
0
0
0
3
4
0
0
0
0
1
1
0
0
0
0
1
1
0
2
2
0
0
0
0
0
2
0
0
0
2
2
0
1
0
0
0
0
1
0
2
4
1
1
0
0
2
0
0
7
0
1
0
0
0
1
1
0
1
0
1
0
0
2
1
0
6
3
0
0
1
0
2
0
0
3
0
1
0
1
0
2
0
0
0
0
1
2
1
4
0
0
0
0
0
0
1
2
2
1
2
2
0
1
1
0
0
0
0
0
1
2
1
4
1
0
4
1
2
1
0
0
0
0
1
2
1
0
0
2
3
1
0
1
1
1
0
1
5
0
1
2
0
2
0
0
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 189ms
memory: 5508kb

input:

30000
11 7 88
4 6 1 2 1 7 3 3 2 6 3
44 60 14 92 55 88 13
11 11 36
8 9 2 9 1 7 1 7 9 3 8
67 13 49 55 23 18 45 33 8 8 66
11 8 10
3 4 6 3 5 3 1 1 7 5 7
4 14 12 15 21 15 11 7
11 5 65
1 5 3 3 5 1 3 4 5 5 1
27 22 18 56 53
11 8 31
7 6 4 3 1 2 5 1 3 2 7
56 64 56 52 1 10 42 38
11 6 90
6 1 5 3 6 2 2 2 3 1 1
8...

output:

0
1
3
1
0
1
0
1
1
1
1
0
2
1
0
2
2
6
0
0
0
3
1
2
1
1
0
0
2
0
1
6
2
0
0
0
0
2
0
0
0
0
2
1
2
1
0
1
0
0
0
1
1
2
5
1
0
0
7
3
1
3
3
2
0
0
0
3
2
2
0
2
2
3
0
1
0
7
4
0
3
0
1
1
5
0
4
1
4
0
1
2
4
0
2
1
0
1
0
0
4
0
0
2
1
0
0
1
0
1
0
0
0
1
1
0
0
5
2
0
0
0
2
0
0
0
2
0
0
0
0
0
1
1
2
3
1
0
0
0
4
4
0
2
0
3
4
0
1
1
...

result:

ok 30000 numbers

Test #4:

score: 0
Accepted
time: 270ms
memory: 5540kb

input:

10000
21 2 301
2 1 1 2 1 1 1 2 1 2 2 2 2 2 2 2 1 2 1 1 2
91 73
21 16 233
1 6 6 8 10 10 9 3 8 8 8 7 11 6 7 11 9 13 13 11 11
29 88 36 42 98 53 65 44 31 58 27 36 34 51 33 26
21 35 699
11 33 22 24 34 33 24 16 5 12 8 26 34 4 1 33 10 3 9 21 10
56 27 39 44 44 53 75 14 57 20 51 69 85 15 29 50 76 79 37 6 17 ...

output:

1
6
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
11
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 10000 numbers

Test #5:

score: -100
Memory Limit Exceeded

input:

10
99999 48959 549895809
17383 33522 48377 31386 19330 13043 27394 37249 36294 12722 8373 37625 12026 13690 14053 30528 16342 31971 17759 23330 19377 6906 2676 9898 35581 3357 38474 28896 7227 46575 20055 8860 38630 48009 37394 20074 31995 24762 36589 33677 5802 16186 22579 2830 43898 14963 41255 30...

output:


result: