# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
32023 | 2017-09-22T13:32:24 Z | chonka | Job Scheduling (CEOI12_jobs) | C++ | 496 ms | 24956 KB |
#include<iostream> #include<stdio.h> #include<vector> #include<queue> using namespace std ; #define MAXN 100007 int n , d , m ; vector < int > v[ MAXN ] ; vector < int > ans[ MAXN ] ; int pos[ 10 * MAXN ] ; int rev[ 10 * MAXN ] ; bool f ( int x ) { queue < pair < int , int > > q ; int i , j , sz ; for ( i = 1 ; i <= n ; i ++ ) { sz = v[ i ].size ( ) ; for ( j = 0 ; j < sz ; j ++ ) { q.push ( make_pair ( v[ i ][ j ] , i + d ) ) ; } ans[ i ].clear ( ) ; int lft = x ; while ( lft != 0 && q.empty ( ) == false ) { pair < int , int > p = q.front ( ) ; if ( p.second < i ) { return false ; } lft -- ; q.pop ( ) ; ans[ i ].push_back ( p.first ) ; } } return true ; } void input ( ) { scanf ( "%d%d%d" , &n , &d , &m ) ; int i ; for ( i = 1 ; i <= m ; i ++ ) { int x ; scanf ( "%d" , &x ) ; v[ x ].push_back ( i ) ; } } void solve ( ) { int l , r , mid ; l = 1 ; r = m ; while ( r - l > 3 ) { mid = ( l + r ) / 2 ; if ( f ( mid ) == true ) { r = mid ; } else { l = mid ; } } while ( f ( l ) == false ) { l ++ ; } f ( l ) ; printf ( "%d\n" , l ) ; int i , j ; int sz ; for ( i = 1 ; i <= n ; i ++ ) { sz = ans[ i ].size ( ) ; for ( j = 0 ; j < sz ; j ++ ) { printf ( "%d " , ans[ i ][ j ] ) ; } printf ( "0\n" ) ; } } int main ( ) { input ( ) ; solve ( ) ; return 0 ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 16436 KB | Output is correct |
2 | Correct | 33 ms | 16436 KB | Output is correct |
3 | Correct | 39 ms | 16436 KB | Output is correct |
4 | Correct | 39 ms | 16436 KB | Output is correct |
5 | Correct | 36 ms | 16436 KB | Output is correct |
6 | Correct | 36 ms | 16436 KB | Output is correct |
7 | Correct | 33 ms | 16436 KB | Output is correct |
8 | Correct | 39 ms | 16436 KB | Output is correct |
9 | Correct | 46 ms | 16004 KB | Output is correct |
10 | Correct | 39 ms | 16028 KB | Output is correct |
11 | Correct | 49 ms | 15572 KB | Output is correct |
12 | Correct | 96 ms | 16668 KB | Output is correct |
13 | Correct | 136 ms | 18744 KB | Output is correct |
14 | Correct | 313 ms | 20752 KB | Output is correct |
15 | Correct | 243 ms | 20196 KB | Output is correct |
16 | Correct | 373 ms | 22032 KB | Output is correct |
17 | Correct | 496 ms | 24956 KB | Output is correct |
18 | Correct | 383 ms | 22968 KB | Output is correct |
19 | Correct | 439 ms | 22968 KB | Output is correct |
20 | Correct | 373 ms | 24956 KB | Output is correct |