fork download
copy 
  1. #define _STRESS
  2. #ifdef STRESS
  3. #include "Base.h"
  4. #else
  5. #pragma comment(linker, "/STACK:66777216")
  6.  
  7. #include <iostream>
  8. #include <vector>
  9. #include <cmath>
  10. #include <algorithm>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. #include <map>
  14. #include <set>
  15. #include <bitset>
  16. #include <ctime>
  17. #include <queue>
  18. #include <deque>
  19. #include <iomanip>
  20. #include <functional>
  21. #include <random>
  22.  
  23. using namespace std;
  24.  
  25. typedef uniform_int_distribution<> uid;
  26. typedef mt19937 rnd_t;
  27.  
  28. typedef long long ll;
  29. typedef pair<int, int> ii;
  30.  
  31. typedef vector<int> vi;
  32. typedef vector<size_t> vsz;
  33.  
  34. typedef vector<ll> vll;
  35. typedef vector<vll> vvll;
  36.  
  37. typedef vector<ii> vii;
  38. typedef vector<vii> vvii;
  39.  
  40. typedef vector<vi> vvi;
  41. typedef vvi graph_t;
  42.  
  43. const char SPACE = ' ', ENDL = '\n';
  44.  
  45. const int BASE = 1000 * 1000 * 1000 + 7;
  46. const int MODULO = BASE; // 1000 * 1000 * 1000 + 31; //998244353
  47. #endif
  48.  
  49. template <class T>
  50. T read() {
  51. 	T value;
  52. 	cin >> value;
  53. 	return value;
  54. }
  55.  
  56. int read_int() {
  57. 	return read<int>();
  58. }
  59.  
  60. size_t read_size() {
  61. 	return read<size_t>();
  62. }
  63.  
  64. ll read_ll() {
  65. 	return read<ll>();
  66. }
  67.  
  68. ii read_ii() {
  69. 	int x = read_int();
  70. 	int y = read_int();
  71. 	return ii(x, y);
  72. }
  73.  
  74. string read_string() {
  75. 	return read<string>();
  76. }
  77.  
  78. template <class T>
  79. void read_vector(vector<T> & a, size_t size) {
  80. 	a.resize(size);
  81. 	for (T & value : a) cin >> value;
  82. }
  83.  
  84. template <class T1, class T2>
  85. void read_pairs(vector<pair<T1, T2>> & a, size_t size) {
  86. 	a.resize(size);
  87. 	for (auto & value : a) cin >> value.first >> value.second;
  88. }
  89.  
  90. void add_to_each(vi & a, int delta) {
  91. 	for (int & value : a) value += delta;
  92. }
  93.  
  94. void add_to_each(vii & a, int delta) {
  95. 	for (ii & value : a) {
  96. 		value.first += delta;
  97. 		value.second += delta;
  98. 	}
  99. }
  100.  
  101. template <class T>
  102. void print(vector<T> & a, char sep = SPACE) {
  103. 	for (T & value : a) cout << value << sep;
  104. 	cout << ENDL;
  105. }
  106.  
  107. void print_pairs(vii & a, char sep = ENDL) {
  108. 	for (ii & value : a) cout << value.first << " " << value.second << sep;
  109. 	if (sep != ENDL) cout << ENDL;
  110. }
  111.  
  112. int get_bit(ll mask, int bit) {
  113. 	return (int)((mask >> bit) & 1);
  114. }
  115.  
  116. ll set_bit(ll mask, int bit) {
  117. 	return mask | (1LL << bit);
  118. }
  119.  
  120. ll clear_bit(ll mask, int bit) {
  121. 	return mask & (~(1LL << bit));
  122. }
  123.  
  124. vi reverse(vi & a) {
  125. 	reverse(a.begin(), a.end());
  126. 	return a;
  127. }
  128.  
  129. typedef ll mod_t;
  130.  
  131. void update_max(int & cur_value, int new_value) {
  132. 	cur_value = max(cur_value, new_value);
  133. }
  134.  
  135. void update_min(int & cur_value, int new_value) {
  136. 	cur_value = min(cur_value, new_value);
  137. }
  138.  
  139. ll gcd(ll a, ll b) {
  140. 	return (a == 0 ? b : gcd(b % a, a));
  141. }
  142.  
  143. ll lcm(ll a, ll b) {
  144. 	return (a * b == 0 ? 0 : a / gcd(a, b) * b);
  145. }
  146.  
  147. bool check_index(int index, int size) {
  148. 	return 0 <= index && index < size;
  149. }
  150.  
  151. bool check_cell(int x, int xSize, int y, int ySize) {
  152. 	return check_index(x, xSize) && check_index(y, ySize);
  153. }
  154.  
  155. // =============================================
  156.  
  157. typedef pair<double, double> ans_t;
  158.  
  159. // =============================================
  160.  
  161. #define RUN
  162.  
  163. void init() {
  164.  
  165. }
  166.  
  167. vector<vector<vector<ans_t>>> dp;
  168.  
  169. vector<vector<double>> p;
  170.  
  171. ans_t f(int cur, int fm, int sm) {
  172. 	if (dp[cur][fm][sm].first != -1) {
  173. 		return dp[cur][fm][sm];
  174. 	}
  175.  
  176. 	int index = cur / 2;
  177. 	int team = cur % 2;
  178.  
  179. 	if (p[0].size() == index) {
  180. 		int fc = 0, sc = 0;
  181. 		for (int i = 0; i < p[0].size(); ++i) {
  182. 			if (get_bit(fm, i)) ++fc;
  183. 		}
  184.  
  185. 		for (int i = 0; i < p[1].size(); ++i) {
  186. 			if (get_bit(sm, i)) ++sc;
  187. 		}
  188.  
  189. 		double wpr = (fc > sc ? 1 : 0);
  190. 		double dpr = (fc == sc ? 1 : 0);
  191.  
  192. 		return (dp[cur][fm][sm] = make_pair(wpr, dpr));
  193. 	}
  194.  
  195. 	if (!get_bit(fm, index)) {
  196. 		ans_t pr = f(cur + 1, sm, fm);
  197.  
  198. 		double dpr = pr.second;
  199. 		double wpr = 1 - dpr - pr.first;
  200.  
  201. 		return dp[cur][fm][sm] = make_pair(wpr, dpr);
  202. 	}
  203.  
  204. 	ans_t best_pr(-1, -1);
  205.  
  206. 	double pr = p[team][index];
  207. 	for (int j = 0; j < p[1 - team].size(); ++j) {
  208. 		if (!get_bit(sm, j)) continue;
  209.  
  210. 		ans_t killed_pr = f(cur + 1, sm ^ (1 << j), fm);
  211. 		ans_t missed_pr = f(cur + 1, sm, fm);
  212.  
  213. 		double dpr = pr * killed_pr.second + (1 - pr) * missed_pr.second;
  214. 		double lpr = pr * killed_pr.first + (1 - pr) * missed_pr.first;
  215. 		double wpr = 1 - dpr - lpr;
  216.  
  217. 		ans_t cur_pr(wpr, dpr);
  218. 		if (best_pr < cur_pr) {
  219. 			best_pr = cur_pr;
  220. 		}
  221. 	}
  222.  
  223. 	return dp[cur][fm][sm] = best_pr;
  224. }
  225.  
  226. ans_t get_answer(int n) {
  227. 	int mask_limit = (1 << n);
  228.  
  229. 	dp.assign(
  230. 		n + n + 1, vector<vector<ans_t>>(
  231. 			mask_limit, vector<ans_t>(
  232. 				mask_limit, { -1, -1 }
  233. 			)
  234. 		)
  235. 	);
  236.  
  237. 	return f(0, mask_limit - 1, mask_limit - 1);
  238. }
  239.  
  240. int main() {
  241. #ifdef RUN
  242. 	ios::sync_with_stdio(false);
  243. 	cin.tie(nullptr);
  244. 	cout.tie(nullptr);
  245.  
  246. 	#ifndef ONLINE_JUDGE
  247. 		freopen("input.txt", "r", stdin);
  248. 		freopen("output.txt", "w", stdout);
  249. 	#endif
  250.  
  251. 	init();
  252.  
  253. 	int tests = 1;// read_size();
  254. 	for (int test = 1; test <= tests; ++test) {
  255. 		int n = read_size();
  256.  
  257. 		p.assign(2, vector<double>());
  258.  
  259. 		read_vector(p[0], n);
  260. 		read_vector(p[1], n);
  261.  
  262. 		ans_t answer = get_answer(n);
  263. 		cout << answer.first << " " << answer.second << ENDL;
  264. 		//cout << answer << ENDL;
  265. 		//print(answer);
  266. 		//for (vi & row : answer) {
  267. 		//	add_to_each(row, 1);
  268. 		//	print(row);
  269. 		//}
  270. 	}
  271. #else
  272. 	set_print_file("tests.txt");
  273. 	stress();
  274. 	close_print_file();
  275. #endif
  276. 	return 0;
  277. }
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
2
0.33 0.33
0.33 0.33
stdout
copy 
0.405174 0.274474
https://ideone.com/TuAlnY
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!