fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <functional>
  6.  
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     ios_base::sync_with_stdio(false);
  12. 	//cin.tie(nullptr);
  13.  
  14.     int serverNum;
  15.     cin >> serverNum;
  16.     vector<vector<int>> servers(serverNum);
  17.  
  18.     int clientNum;
  19.     cin >> clientNum;
  20.     vector<int> serverAllocations(clientNum);
  21.  
  22.     for (int i = 0; i < clientNum; ++i)
  23.     {
  24.         int start, end;
  25.         cin >> start >> end;
  26.         int minAmount = 999999999;
  27.         int preferredServerIndex = 0;
  28.         for (int j = 0; j < serverNum; ++j)
  29.         {
  30.             int amount = distance(upper_bound(servers[j].begin(), servers[j].end(), start), servers[j].end());
  31.             if (amount < minAmount)
  32.             {
  33.                 preferredServerIndex = j;
  34.                 minAmount = amount;
  35.             }
  36.         }
  37.         serverAllocations[i] = preferredServerIndex;
  38.         servers[preferredServerIndex].push_back(end);
  39.         push_heap(servers[preferredServerIndex].begin(), servers[preferredServerIndex].end(), greater<int>());
  40.         //for (int i: servers[preferredServerIndex]) cout << i << ' ';
  41.         //cout << '\n';
  42.     }
  43.     int queries;
  44.     cin >> queries;
  45.     while (queries--)
  46.     {
  47.         int query;
  48.         cin >> query;
  49.         cout << serverAllocations[query - 1] + 1  << '\n';
  50.     }
  51. }
Success #stdin #stdout 0s 4948KB
comments (?)
stdin 
3
8
0 5
0 2
2 5
6 10
7 9
7 15
9 20
9 11
3
3
6
8
stdout 
2
3
1
https://ideone.com/BzYTjD
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!