fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll; const int N = 50000; ll elapsed_time[ N + 1 ]; typedef vector< int > vector_t;
  6.  
  7. struct pending_tasks_t: vector_t
  8. {
  9. int order( int i )
  10. {
  11. return lower_bound( begin(), end(), i ) - begin();
  12. }
  13.  
  14. void remove_task( int i )
  15. {
  16. erase( lower_bound( begin(), end(), i ) );
  17. }
  18. };
  19.  
  20. struct pending_tasks_map_t: map< int, vector_t >
  21. {
  22. void round_robin( ll time, pending_tasks_t& pending_tasks )
  23. {
  24. ll p = pending_tasks.size();
  25.  
  26. for( int key, elapsed_cycles = 2; not empty(); elapsed_cycles = key + 1 )
  27. {
  28. auto it = begin(); time += ( ( key = it->first ) - elapsed_cycles ) * p + 1;
  29.  
  30. for( auto i: it->second )
  31. elapsed_time[ i ] = time + pending_tasks.order( i );
  32.  
  33. for( auto i: it->second )
  34. pending_tasks.remove_task( i );
  35.  
  36. time += p - 1, p -= it->second.size(), erase( it );
  37. }
  38. }
  39. };
  40.  
  41. int main()
  42. {
  43. ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  44.  
  45. int n; cin >> n; pending_tasks_t pending_tasks; pending_tasks_map_t pending_tasks_map;
  46.  
  47. for( int i = 1; i <= n; i++ )
  48. {
  49. int t; cin >> t;
  50.  
  51. if ( t == 1 )
  52. elapsed_time[ i ] = i;
  53. else
  54. pending_tasks_map[ t ].push_back( i ), pending_tasks.push_back( i );
  55. }
  56.  
  57. pending_tasks_map.round_robin( n, pending_tasks );
  58.  
  59. for( int i = 1; i <= n; i++ )
  60. cout << elapsed_time[ i ] << '\n';
  61. }
Success #stdin #stdout 0s 15624KB
stdin
5
8
1
3
3
8
stdout
22
2
11
12
23