# CFR 767 D. Cartons of milk ( Binary Search, Counting Sort )

Problem - D - Codeforces

N, M ≤ 1e6

TL: 2000 ms
ML: 256 MB

O( 過期天數 * lg M ) / O( 過期天數 )

``` #include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;
const int MAXM = ( int ) 1e6;

int N, M, K;
int refg[ MAXN ];
int shop[ MAXM ];
int sord[ MAXM ];

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> M >> K;
for( int i = 0; i < N; ++i ){
cin >> refg[ i ];
}
for( int i = 0; i < M; ++i ){
cin >> shop[ i ];
sord[ i ] = i;
}
sort( sord, sord + M, [ & ]( int i, int j ){ return shop[ i ] > shop[ j ]; } );
}
{
int ans = -1;
for( int lb = 0, rb = M; lb <= rb; ){
int mid = lb + rb >> 1;
static int milk[ ( int ) 1e7 + 1 ];
for( int i = 0; i < N; ++i ){
++milk[ refg[ i ] ];
}
for( int i = 0; i < mid; ++i ){
++milk[ shop[ sord[ i ] ] ];
}
int ng = 0;
vector< int > gat;
for( int i = 0; i <= ( int ) 1e7; ++i ){
for( int j = 0; j < milk[ i ]; ++j ){
gat.emplace_back( i );
}
}
for( int i = 0; i < N + mid; i += K ){
ng |= gat[ i ] < i / K;
}
if( not ng ){
ans = mid;
lb = mid + 1;
} else{
rb = mid - 1;
}
for( int i = 0; i < N; ++i ){
--milk[ refg[ i ] ];
}
for( int i = 0; i < mid; ++i ){
--milk[ shop[ sord[ i ] ] ];
}
}
cout << ans << endl;
if( ans != -1 ){
for( int i = 0; i < ans; ++i ){
cout << sord[ i ] + 1 << " \n"[ i + 1 == ans ];
}
}
}
return 0;
}
```