fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <stdio.h>
  4. #include <string>
  5. #include <set>
  6. #include <fstream>
  7. #include <algorithm>
  8. #include <math.h>
  9. #include <map>
  10. #include <queue>
  11. #include <bitset>
  12.  
  13. using namespace std;
  14.  
  15. const int INF = 1e9;
  16.  
  17. queue <int> q[100000];
  18.  
  19. int S[100000], n, m, queue_time, queue_sum, out, current_time;
  20.  
  21. vector <int> g[100000];
  22.  
  23. set <pair <int, int> > s;
  24.  
  25. bool Comp (int a, int b)
  26. {
  27. 	return S[a] < S[b];
  28. }
  29.  
  30. int main ()
  31. {
  32. 	cin >> m;
  33.  
  34. 	for (int i = 0; i <= m; i++)
  35. 		scanf ("%d", &S[i]);
  36.  
  37. 	for (int i = 1; i < m; i++)
  38. 	{
  39. 		char c = ' ';
  40. 		int a;
  41.  
  42. 		while (c != '\n')
  43. 		{
  44. 			scanf ("%d%c", &a, &c);
  45. 			g[i].push_back (a);
  46. 		}
  47.  
  48. 		sort (g[i].begin (), g[i].end (), Comp);
  49. 	}
  50.  
  51. 	g[0].push_back (1);
  52. 	g[m].push_back (m + 1);
  53.  
  54. 	cin >> n;
  55.  
  56. 	for (int i = 1; i <= n; i++)
  57. 	{
  58. 		q[0].push (i);
  59. 		s.insert (make_pair (S[0], 0));
  60. 	}
  61.  
  62. 	while (out != n)
  63. 	{
  64. 		pair <int, int> top = *s.begin ();
  65. 		current_time = top.first;
  66. 		int server = top.second, query = q[server].front ();
  67.  
  68. 		printf ("Query %d left server %d at time %d\n", query, server, current_time);
  69.  
  70. 		q[server].pop ();
  71. 		s.erase (s.begin ());
  72. 		if (!q[server].empty ())
  73. 		{
  74. 			s.insert (make_pair (current_time + S[server], server));
  75. 		}
  76.  
  77. 		if (server == m)
  78. 		{
  79. 			out++;
  80. 			continue;
  81. 		}
  82.  
  83. 		int index, mn = INF;
  84.  
  85. 		for (int i = 0; i < g[server].size (); i++)
  86. 		{
  87. 			int to = g[server][i];
  88.  
  89. 			if (S[to] * (q[to].size () + 1) < mn)
  90. 			{
  91. 				mn = S[to] * (q[to].size () + 1);
  92. 				index = to;
  93. 			}
  94. 		}
  95.  
  96. 		if (q[index].size ()) queue_sum += S[index] * (q[index].size () - 1) * (q[index].size () - 1);
  97. 		if (q[index].size ()) queue_time += S[index] * (q[index].size () - 1);
  98.  
  99. 		q[index].push (query);
  100. 		if (q[index].size () == 1)
  101. 		{
  102. 			s.insert (make_pair (current_time + S[index], index));
  103. 		}
  104. 	}
  105.  
  106. 	if (queue_time) printf ("Average Lq = %lf\n", (double) queue_sum / (double) queue_time);
  107. 	printf ("Average time in queue = %lf", (double) queue_time / (double) n);
  108.  
  109. }
Success #stdin #stdout 0.02s 85056KB
comments (?)
stdin
copy 
1
1 
2
10
stdout
copy 
Query 1 left server 0 at time 1
Query 2 left server 0 at time 2
Query 3 left server 0 at time 3
Query 1 left server 1 at time 3
Query 4 left server 0 at time 4
Query 5 left server 0 at time 5
Query 2 left server 1 at time 5
Query 6 left server 0 at time 6
Query 7 left server 0 at time 7
Query 3 left server 1 at time 7
Query 8 left server 0 at time 8
Query 9 left server 0 at time 9
Query 4 left server 1 at time 9
Query 10 left server 0 at time 10
Query 5 left server 1 at time 11
Query 6 left server 1 at time 13
Query 7 left server 1 at time 15
Query 8 left server 1 at time 17
Query 9 left server 1 at time 19
Query 10 left server 1 at time 21
Average Lq = 3.000000
Average time in queue = 4.000000
https://ideone.com/zw49Sm
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!