fork download
copy 
  1. //version1
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef pair<int,int> pii;
  5. typedef long double ld;
  6. #define points first
  7. #define time second
  8.  
  9. bool paradox(vector<vector<pii>> & w, ld c) {
  10. 	ld time_total = 0;
  11. 	for(auto group : w) for(pii p : group)
  12. 		time_total += p.time;
  13. 	ld time_so_far = 0;
  14. 	vector<pair<int,pair<ld,ld>>> all;
  15. 	for(vector<pii> & group : w) {
  16. 		ld time_this_group = 0;
  17. 		for(pii & p : group)
  18. 			time_this_group += p.time;
  19. 		for(pii & p : group) {
  20. 			ld small = p.points * (1 - c * (time_so_far + time_this_group) / time_total);
  21. 			ld big = p.points * (1 - c * (time_so_far + p.time) / time_total);
  22. 			all.push_back(make_pair(p.points, make_pair(small, big)));
  23. 		}
  24. 		time_so_far += time_this_group;
  25. 	}
  26. 	sort(all.begin(), all.end());
  27. 	ld max_so_far = -1;
  28. 	for(int i = 0; i < (int) all.size(); ++i) {
  29. 		int j = i;
  30. 		while(j + 1 < (int) all.size() && all[j+1].first == all[i].first)
  31. 			++j;
  32. 		for(int k = i; k <= j; ++k)
  33. 			if(all[k].second.first < max_so_far)
  34. 				return true; // paradox
  35. 		for(int k = i; k <= j; ++k)
  36. 			max_so_far = max(max_so_far, all[k].second.second);
  37. 		i = j;
  38. 	}
  39.  
  40. 	return false;
  41. }
  42.  
  43.  
  44. int cmp(const pii & a, const pii & b) { // -1, 0 or 1
  45. 	long long tmp = (long long) a.first * b.second - (long long) a.second * b.first;
  46. 	if(tmp > 0) return -1;
  47. 	if(tmp == 0) return 0;
  48. 	return 1;
  49. }
  50. bool sort_cmp(const pii & a, const pii & b) {
  51. 	int memo = cmp(a, b);
  52. 	return memo == -1 || (memo == 0 && a.points < b.points);
  53. }
  54.  
  55. const int nax = 1e6 + 5;
  56. pii in[nax];
  57.  
  58. int main() {
  59. 	int n;
  60. 	scanf("%d", &n);
  61. 	for(int i = 0; i < n; ++i)
  62. 		scanf("%d", &in[i].points);
  63. 	for(int i = 0; i < n; ++i)
  64. 		scanf("%d", &in[i].time);
  65. 	sort(in, in + n, sort_cmp);
  66. 	vector<vector<pii>> w;
  67. 	for(int i = 0; i < n; ++i) {
  68. 		if(i == 0 || cmp(in[i-1], in[i]) != 0)
  69. 			w.push_back(vector<pii>{});
  70. 		w.back().push_back(in[i]);
  71. 	}
  72. 	ld low = 0, high = 1;
  73. 	for(int rep = 0; rep < 40; ++rep) {
  74. 		ld mid = (low + high) / 2;
  75. 		if(paradox(w, mid)) high = mid;
  76. 		else low = mid;
  77. 	}
  78. 	printf("%.10lf\n", (double) (low + high) / 2);
  79. 	return 0;
  80. }
  81.  
  82. // version2
  83. #include <bits/stdc++.h>
  84. using namespace std;
  85.  
  86. int n;
  87.  
  88. pair <long long,long long> tab[1000007];
  89.  
  90. vector <int> dos1, dos2;
  91.  
  92. int k;
  93. int scale[1000007];
  94.  
  95. double maxi[1000007];
  96. double mini[1000007];
  97.  
  98. double bsa, bsb=1.0, bss;
  99.  
  100. long long sum[1000007];
  101.  
  102. int it;
  103.  
  104. int czy;
  105.  
  106. bool mniej(pair <long long,long long> a, pair <long long,long long> b)
  107. {
  108.     return a.first*b.second>b.first*a.second;
  109. }
  110.  
  111. long long que(int a, int b)
  112. {
  113.     return sum[b]-sum[a-1];
  114. }
  115.  
  116.  
  117. int main()
  118. {
  119.     scanf("%d", &n);
  120.     for (int i=1; i<=n; i++)
  121.     {
  122.         scanf("%lld", &tab[i].first);
  123.     }
  124.     for (int i=1; i<=n; i++)
  125.     {
  126.         scanf("%lld", &tab[i].second);
  127.     }
  128.     sort(tab+1, tab+1+n, mniej);
  129.     for (int i=1; i<=n; i++)
  130.     {
  131.         dos2.push_back(tab[i].first);
  132.     }
  133.     sort(dos2.begin(), dos2.end());
  134.     for (int i=0; i<n; i++)
  135.     {
  136.         if (!i || dos2[i]!=dos2[i-1])
  137.         {
  138.             dos1.push_back(dos2[i]);
  139.         }
  140.     }
  141.     k=dos1.size();
  142.     for (int i=1; i<=n; i++)
  143.     {
  144.         scale[i]=lower_bound(dos1.begin(), dos1.end(), tab[i].first)-dos1.begin()+1;
  145.     }
  146.     for (int i=1; i<=n; i++)
  147.     {
  148.         sum[i]=sum[i-1]+tab[i].second;
  149.     }
  150.     for (int h=1; h<=100; h++)
  151.     {
  152.         bss=(bsa+bsb)/2.0;
  153.         for (int i=1; i<=k; i++)
  154.         {
  155.             mini[i]=1000000000.0;
  156.             maxi[i]=0.0;
  157.         }
  158.         it=0;
  159.         for (int i=1; i<=n; i++)
  160.         {
  161.             while(it+1<i && mniej(tab[it+1], tab[i]))
  162.             it++;
  163.             maxi[scale[i]]=max(maxi[scale[i]], tab[i].first*(1.0-bss*(que(1, it)+tab[i].second)/sum[n]));
  164.         }
  165.         it=n+1;
  166.         for (int i=n; i; i--)
  167.         {
  168.             while(it-1>i && mniej(tab[i], tab[it-1]))
  169.             it--;
  170.             mini[scale[i]]=min(mini[scale[i]], tab[i].first*(1.0-bss*que(1, it-1)/sum[n]));
  171.         }
  172.         czy=0;
  173.         for (int i=2; i<=k; i++)
  174.         {
  175.             if (mini[i]<maxi[i-1])
  176.             {
  177.                 czy=1;
  178.             }
  179.         }
  180.         if (czy)
  181.         {
  182.             bsb=bss;
  183.         }
  184.         else
  185.         {
  186.             bsa=bss;
  187.         }
  188.     }
  189.     printf("%.11lf\n", bss);
  190.     return 0;
  191. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:117:5: error: redefinition of 'int main()'
 int main()
     ^
prog.cpp:58:5: note: 'int main()' previously defined here
 int main() {
     ^
stdout
copy 
Standard output is empty
https://ideone.com/OoSLF3
language:
C++14 (gcc 8.3)
created:
8 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!