fork download
copy 
  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
comments (?)
stdin
copy 
5
8
1
3
3
8
stdout
copy 
22
2
11
12
23
https://ideone.com/UQuoz7
problem RRSCHED, based on SPOJ submission 22542465 (CPP14), 2018-10-20 00:04:42
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!