fork download 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <functional>
  4. #include <iostream>
  5. #include <cfloat>
  6. #include <climits>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <cmath>
  10. #include <map>
  11. #include <unordered_map>
  12. #include <queue>
  13. #include <set>
  14. #include <sstream>
  15. #include <stack>
  16. #include <string>
  17. #include <time.h>
  18. #include <vector>
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22. typedef long double ld;
  23. typedef unsigned long long ull;
  24. typedef pair<int, int> pii;
  25. typedef pair<long long, long long> pll;
  26. typedef pair<double, long long> pdl;
  27.  
  28. const long double pi = 3.141592653589793;
  29.  
  30. #define debug(x) cout << #x << " = " << (x) << endl;
  31. #define rep(i, n) for(int i = 0;i < n;i++)
  32. #define pb push_back
  33. #define mp make_pair
  34. #define mod 1000000007
  35.  
  36. ll power(ll a, ll b) {
  37. 	if (b == 0) return 1;
  38. 	ll pp = power(a, b/2);
  39. 	pp = (pp*pp) % mod;
  40. 	if(b%2 == 0) return pp;
  41. 	return (pp*a)%mod;
  42. }
  43.  
  44. ll A[1000][10];
  45. ll solved[10];
  46. ll n;
  47. vector<vector<ll> > dp;
  48.  
  49. ll help(ll sby, ll i) {
  50. 	long double z = sby*1.0/(n+i);
  51. 	if(z > 1.0/2) {
  52. 		return 2*sby-n-1;
  53. 	}
  54. 	if(z > 1.0/4) {
  55. 		return 4*sby-n-1;
  56. 	}
  57. 	if(z > 1.0/8) {
  58. 		return 8*sby-n-1;
  59. 	}
  60. 	if(z > 1.0/16) {
  61. 		return 16*sby-n-1;
  62. 	}
  63. 	if(z > 1.0/32) {
  64. 		return 32*sby-n-1;
  65. 	}
  66. 	return mod;
  67. }
  68.  
  69. void qupdate(ll sby) {
  70. 	// solved by sby out of n
  71. 	vector<ll> B;
  72. 	ll i = 0;
  73. 	ll j = help(sby, i);
  74. 	while (j <= mod) {
  75. 		B.pb(j);
  76. 		//cout<<i<<" "<<j<<endl;
  77. 		if(j == mod) break;
  78. 		i = j+1;
  79. 		j = help(sby, i);
  80. 	}
  81. 	if(B.size() > 0) dp.pb(B);
  82. }
  83.  
  84. ll points(ll sby, ll i) {
  85. 	long double z = sby*1.0/(n+i);
  86. 	if(z > 1.0/2) {
  87. 		return 500;
  88. 	}
  89. 	if(z > 1.0/4) {
  90. 		return 1000;
  91. 	}
  92. 	if(z > 1.0/8) {
  93. 		return 1500;
  94. 	}
  95. 	if(z > 1.0/16) {
  96. 		return 2000;
  97. 	}
  98. 	if(z > 1.0/32) {
  99. 		return 2500;
  100. 	}
  101. 	return 3000;
  102. }
  103.  
  104. ll playerA(ll i) {
  105. 	ll score = 0;
  106. 	rep(j, 5) {
  107. 		if(A[0][j] != -1) {
  108. 			ll z;
  109. 			if(A[1][j] == -1 || A[0][j] < A[1][j])
  110. 			 	z = points(solved[j], i);
  111. 			else z = points(solved[j]+i, i);
  112. 			score += (z/250)*(250-A[0][j]);
  113. 		}
  114. 	}
  115. 	return score;
  116. }
  117.  
  118. ll playerB(ll i) {
  119. 	ll score = 0;
  120. 	rep(j, 5) {
  121. 		if(A[1][j] != -1) {
  122. 			ll z;
  123. 			if(A[0][j] == -1 || A[0][j] < A[1][j])
  124. 			 	z = points(solved[j], i);
  125. 			else z = points(solved[j]+i, i);
  126. 			score += (z/250)*(250-A[1][j]);
  127. 		}
  128. 	}
  129. 	return score;
  130. }
  131.  
  132. int main() {
  133.     //freopen("input.in","r",stdin);
  134.   	//freopen("output.out","w",stdout);
  135.  
  136. 	cin>>n;
  137. 	rep(i, n) {
  138. 		rep(j, 5) cin>>A[i][j];
  139. 	}
  140.  
  141. 	rep(i, 5) {
  142. 		ll counter = 0;
  143. 		rep(j, n) if(A[j][i] != -1) counter++;
  144. 		solved[i] = counter;
  145. 	}
  146.  
  147. 	rep(i, 5) {
  148. 		if(A[0][i] == -1 and A[1][i] != -1) {
  149. 			qupdate(solved[i]);
  150. 		}
  151. 	}
  152.  
  153. 	vector<ll> C(1, -1);
  154. 	vector<int> tex(dp.size(), 0);
  155. 	while (true) {
  156. 		ll minm = LONG_LONG_MAX;
  157. 		rep(i, dp.size()) {
  158. 			if(tex[i] < dp[i].size()) minm = min(minm, dp[i][tex[i]]);
  159. 		}
  160.  
  161. 		if(minm == LONG_LONG_MAX) break;
  162. 		C.pb(minm);
  163. 		rep(i, dp.size()) {
  164. 			if(tex[i] < dp[i].size() and dp[i][tex[i]] == minm) tex[i]++;
  165. 		}
  166. 	}
  167.  
  168. 	if(C.size() == 1) C.pb(mod);
  169.  
  170. 	//rep(i, C.size()) cout<<C[i]<<" ";cout<<endl;
  171.  
  172. 	for(int i = 1;i < C.size();i++) {
  173. 		ll s = C[i-1]+1;
  174. 		ll e = C[i];
  175. 		ll mid = (s+e)/2;
  176.  
  177. 		ll minm = LONG_LONG_MAX;
  178. 		while (s <= e) {
  179. 			ll sA = playerA(mid);
  180. 			ll sB = playerB(mid);
  181. 			if(sA > sB) minm = min(minm, mid), e = mid-1;
  182. 			else s = mid+1;
  183. 			mid = (s+e)/2;
  184. 		}
  185. 		if(minm != LONG_LONG_MAX) {
  186. 			cout<<minm<<endl;
  187. 			return 0;
  188. 		}
  189. 	}
  190. 	cout<<"-1"<<endl;
  191.  
  192. 	return 0;
  193. }
  194.  
Success #stdin #stdout 0s 15320KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/GbU8vH
language:
C++14 (clang 8.0)
created:
7 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!