fork download
copy 
  1. /*
  2. 	Optimal solution O(N log N)
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. #define maxn 100005
  7. using namespace std;
  8.  
  9. double allocation[maxn];
  10. int a[maxn], b[maxn], d[maxn], N, B;
  11.  
  12. double inf = 1e12;
  13.  
  14. vector< pair<double, int> > orders;
  15.  
  16. void solve() {
  17. 	double remain = B;
  18. 	for (int i = 1; i <= N; i++) {
  19. 		allocation[i] = a[i];
  20. 		remain -= a[i];
  21. 	}
  22.  
  23. 	set<int> activeIndices;
  24. 	double totalWeight = 0, totalMinAllocation = 0;
  25.  
  26. 	for (int i = 0; i < 2 * N; i++) {
  27. 		double currentRatio = orders[i].first, nextRatio = orders[i + 1].first;
  28. 		int idx = abs(orders[i].second);
  29. 		if (orders[i].second < 0) {
  30. 			activeIndices.insert(idx);
  31. 			totalWeight += d[idx];
  32. 			totalMinAllocation += a[idx];
  33. 		} else {
  34. 			activeIndices.erase(idx);
  35. 			allocation[idx] = b[idx];
  36. 			remain -= (b[idx] - a[idx]);
  37.  
  38. 			totalWeight -= d[idx];
  39. 			totalMinAllocation -= a[idx];
  40. 		}
  41.  
  42. 		if (nextRatio >= inf || (remain + totalMinAllocation) <= nextRatio * totalWeight) {
  43. 			double totalAmount = remain + totalMinAllocation;
  44. 			for (auto& id : activeIndices) {
  45. 				allocation[id] = totalAmount * d[id] / totalWeight;
  46. 			}
  47. 			return;
  48. 		}
  49. 	}
  50. }
  51.  
  52. int main() {
  53. 	scanf("%d %d", &N, &B);
  54. 	for (int i = 1; i <= N; i++) {
  55. 		scanf("%d %d %d", &a[i], &b[i], &d[i]);
  56. 		orders.push_back(make_pair(1.0 * a[i] / d[i], -i));
  57. 		orders.push_back(make_pair(1.0 * b[i] / d[i], i));
  58. 	}
  59. 	orders.push_back(make_pair(inf, 0));
  60. 	sort(orders.begin(), orders.end());
  61.  
  62. 	solve();
  63. 	for (int i = 1; i <= N; i++) {
  64. 		printf("%.9f\n", allocation[i]);
  65. 	}
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 4340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RLUOCS
language:
C++14 (gcc 8.3)
created:
4 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!