fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6. typedef unsigned long long ULL;
  7. typedef unsigned int uint;
  8. typedef unsigned short ushort;
  9. typedef pair<int, int> PII;
  10.  
  11. #define MAX_INT (int)0x7fffffff
  12. #define MIN_INT (int)0x80000000
  13. #define MAX_UINT (uint)0xffffffff
  14.  
  15. #define TTi template<typename T> inline
  16. TTi T SQR(T x) { return x * x; }
  17.  
  18. #define CONCAT3_NX(x, y, z) x ## y ## z
  19. #define CONCAT3(x, y, z) CONCAT3_NX(x, y, z)
  20. #define VAR(name) CONCAT3(__tmpvar__, name, __LINE__)
  21. #define TYPE(x) __typeof(x)
  22.  
  23. #define FOR(i, s, n)  for (TYPE(n) i=(s),   VAR(end)=(n);  i <  VAR(end);  i++)
  24. #define RFOR(i, s, n) for (TYPE(n) i=(n)-1, VAR(end)=(s);  i >= VAR(end);  i--)
  25. #define FORN(i, n)    FOR(i, 0, n)
  26. #define RFORN(i, n)   RFOR(i, 0, n)
  27. #define FOREACH(i, v) for (auto& i: v)
  28.  
  29. #define SC() scanf("\n")
  30. #define SC1(fmt, a) scanf(fmt, &a)
  31. #define SC2(fmt, a, b) scanf(fmt, &a, &b)
  32. #define SC3(fmt, a, b, c) scanf(fmt, &a, &b, &c)
  33. #define SCi(a) scanf("%d", &a)
  34. #define SCii(a,b) scanf("%d%d", &a, &b)
  35. #define SCiii(a,b,c) scanf("%d%d%d", &a, &b, &c)
  36. #define fLL "%lld"
  37. #define SCl(a) scanf(fLL, &a)
  38. #define SCll(a,b) scanf(fLL fLL, &a, &b)
  39. #define SClll(a,b,c) scanf(fLL fLL fLL, &a, &b, &c)
  40. #define SCs(s, n) {scanf("%s", s); n = strlen(s);}
  41. #define SCc(s) scanf("%c", &c)
  42.  
  43. #define MP make_pair
  44. #define PB push_back
  45. #define WHOLE(x) (x).begin(),(x).end()
  46. #define SZ(x) ((int)(x).size())
  47. #define POPST(stack) (stack).top();(stack).pop();
  48. #define POPQ(queue) (queue).front();(queue).pop();
  49. #define CONTAINS(v, x) (find(WHOLE(v), (x)) != v.end())
  50. #define SORT(v) (sort(WHOLE(v)))
  51.  
  52. #define LIMIT(x, lim) {if (x > lim) x = lim;}
  53. TTi T MIN(T x, T y) { return (x < y) ? x : y; }
  54. TTi T MAX(T x, T y) { return (x > y) ? x : y; }
  55. TTi T ABS(T x) { return (x > 0) ? x : -x; }
  56. TTi void UPDATE_MIN(T &x, T y) {if (y < x) {x = y;}}
  57. TTi void UPDATE_MAX(T &x, T y) {if (x < y) {x = y;}}
  58. TTi int ARGMAX(T cont) { return max_element(cont.begin(), cont.end()) - cont.begin(); }
  59. TTi int ARGMIN(T cont) { return min_element(cont.begin(), cont.end()) - cont.begin(); }
  60.  
  61. vector<string> split(const string& s, char c) {
  62.     vector<string> v; stringstream ss(s); string x;
  63.     while (getline(ss, x, c)) v.emplace_back(x); return move(v);
  64. }
  65. template<typename T, typename... Args>
  66. inline string arrStr(T arr, int n) {
  67.     stringstream s;
  68.     s << "[";
  69.     FORN(i, n - 1) s << arr[i] << ",";
  70.     s << arr[n - 1] << "]";
  71.     return s.str();
  72. }
  73.  
  74. // #ifndef ONLINE_JUDGE
  75. #ifdef JUDGE_LOCAL
  76.     #define EPR(args...)   if (DEBUG) {fprintf(stderr, args);}
  77.     #define EARR(arr, n)   if (DEBUG) {FORN(i, n) fprintf(stderr, "%d, ", arr[i]);}
  78.     #define EVEC(arr)      if (DEBUG) {FORN(i, arr.size()) fprintf(stderr, "%d, ", arr[i]);}
  79.     #define EVARS(args...) if (DEBUG) { __evars_begin(__LINE__); __evars(split(#args, ',').begin(), args);}
  80.  
  81.     inline void __evars_begin(int line) { cerr << "#" << line << ": "; }
  82.     inline void __evars(vector<string>::iterator it) {cerr << endl;}
  83.  
  84.     TTi void __evars_out_var(vector<T> val) {
  85.         cerr << arrStr(val, val.size());
  86.     }
  87.     TTi void __evars_out_var(T* val) {
  88.         cerr << arrStr(val, 10);
  89.     }
  90.     TTi void __evars_out_var(T val) {
  91.         cerr << val;
  92.     }
  93.     template<typename T, typename... Args>
  94.     inline void __evars(vector<string>::iterator it, T a, Args... args) {
  95.         cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  96.         __evars_out_var(a);
  97.         cerr << "; ";
  98.         __evars(++it, args...);
  99.     }
  100. #else
  101.     #define EPR(args...) 1
  102.     #define EARR(args...) 1
  103.     #define EVEC(args...) 1
  104.     #define EVARS(args...) 1
  105. #endif
  106.  
  107. template<class T> inline string TOSTR(const T & x) { stringstream ss; ss << x; return ss.str(); }
  108. #define DIE(args...) {printf(args);exit(0);}
  109. inline void PR(void) {}
  110. inline void PR(int x) {printf("%d", x);}
  111. inline void PR(LL x) {printf("%lld", x);}
  112. inline void PR(char * s) {printf("%s", s);}
  113. inline void PR(const char * s) {printf("%s", s);}
  114. inline void PR(double f) {printf("%.10lf", f);}
  115. inline void PR(long double f) {printf("%.10llf", f);}
  116. inline void PR(vector<int> &vec) {for(auto x: vec){PR(x);putc(0x20,stdout);}}
  117. TTi void PRS(T x) {PR(x);putc(0x20,stdout);}
  118. TTi void PRN(T x) {PR(x);putc(0x0a,stdout);}
  119. void PRN(void) {putc(0x0a,stdout);}
  120.  
  121. inline int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
  122. inline LL gcd(LL a, LL b) { return a ? gcd(b % a, a) : b; }
  123. inline LL powmod(LL a, LL p, LL m) { LL r = 1; while (p) { if (p & 1) r = r*a%m; p>>=1; a=a*a%m; } return r; }
  124.  
  125. struct pairhash {
  126.     template <typename T, typename U>
  127.     std::size_t operator() (const std::pair<T, U> &x) const {
  128.         return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  129.     }
  130. };
  131.  
  132. template <typename K, typename V>
  133. V GetWithDef(const std::map<K,V> & m, const K & key, const V & defval ) {
  134.     auto it = m.find(key);
  135.     return (it == m.end()) ? defval : it->second;
  136. }
  137.  
  138. template <typename K, typename V>
  139. void SetDef(std::map<K,V> & m, const K & key, const V & defval ) {
  140.     auto it = m.find(key);
  141.     if (it == m.end()) m[key] = defval;
  142. }
  143.  
  144. template <typename K, typename V>
  145. V GetWithDef(const std::unordered_map<K,V> & m, const K & key, const V & defval ) {
  146.     auto it = m.find(key);
  147.     return (it == m.end()) ? defval : it->second;
  148. }
  149.  
  150. template <typename K, typename V>
  151. void SetDef(std::unordered_map<K,V> & m, const K & key, const V & defval ) {
  152.     auto it = m.find(key);
  153.     if (it == m.end()) m[key] = defval;
  154. }
  155.  
  156. const int MOD = 1000 * 1000 * 1000 + 7;
  157. const double PI = 3.1415926535897932384626433832795l;
  158.  
  159. inline void addto(int &a, int b) {
  160.     a += b;
  161.     if (a >= MOD) a -= MOD;
  162. }
  163. inline int add(int a, int b) {
  164.     a += b;
  165.     if (a >= MOD) a -= MOD;
  166.     return a;
  167. }
  168. inline void subto(int &a, int b) {
  169.     a -= b;
  170.     if (a < 0) a += MOD;
  171.     if (a >= MOD) a -= MOD;
  172. }
  173. inline int sub(int a, int b) {
  174.     a -= b;
  175.     if (a < 0) a += MOD;
  176.     if (a >= MOD) a -= MOD;
  177.     return a;
  178. }
  179. inline void multo(int &a, int b) {
  180.     a = (long long)a * b % MOD;
  181. }
  182. inline int mul(int a, int b) {
  183.     return (long long)a * b % MOD;
  184. }
  185. inline int mulmod(int a, int b, int mod) {
  186.     return (long long)a * b % mod;
  187. }
  188. inline int powmod(int a, int e, int mod) {
  189.     int x;
  190.     for(x = 1; e > 0; e >>= 1) {
  191.         if (e & 1)
  192.             x = mulmod(x, a, mod);
  193.         a = mulmod(a, a, mod);
  194.     }
  195.     return x;
  196. }
  197. inline int invmod_prime(int a, int mod) {
  198.     return powmod(a, mod - 2, mod);
  199. }
  200. inline LL invmod_LL(LL p){
  201.     LL q=p;
  202.     for(LL a=p*p;a!=1;a*=a) q*=a;
  203.     return q;
  204. }
  205.  
  206.  
  207.  
  208. // -----------------------------------------------------------------
  209. // CODE
  210. // -----------------------------------------------------------------
  211.  
  212. #define DEBUG 1
  213.  
  214. int N, M, K, L, E, Q;
  215. double pwin[100][100];
  216.  
  217. bool visited[1 << 18] = {};
  218. double cache[1 << 18] = {};
  219.  
  220. double solve(int mask) {
  221.     if (!(mask & 1)) return 0.0;
  222.     if (mask == 1) return 1.0;
  223.  
  224.     if (!visited[mask]) {
  225.         double res = 0;
  226.         int bestI = -1, bestJ = -1;
  227.         FORN(i, N) {
  228.             if ( !(mask & (1 << i)) ) continue;
  229.             FOR(j, 1, N) {
  230.                 if (i == j) continue;
  231.                 if ( !(mask & (1 << j)) ) continue;
  232.                 int mask1 = mask ^ (1 << i);
  233.                 double prob1 = pwin[j][i];
  234.                 int mask2 = mask ^ (1 << j);
  235.                 double prob2 = pwin[i][j];
  236.                 double t = prob1 * solve(mask1) + prob2 * solve(mask2);
  237.                 if (t > res) {
  238.                     res = t;
  239.                     bestI = i;
  240.                     bestJ = j;
  241.                 }
  242.             }
  243.         }
  244.         cout << "for mask " << mask << ": " << bestI + 1 << " " << bestJ + 1 << endl;
  245.         cache[mask] = res;
  246.         visited[mask] = 1;
  247.     }
  248.     return cache[mask];
  249. }
  250.  
  251. int main() {
  252.     ios_base::sync_with_stdio(0);
  253.  
  254.     SCi(N);
  255.     FORN(i, N) {
  256.     FORN(j, N) {
  257.         scanf("%lf", &pwin[i][j]);
  258.         EVARS(pwin[i][j]);
  259.     }}
  260.  
  261.     int mask = (1 << N) - 1;
  262.     double ans = solve(mask);
  263.  
  264.     for (int i = 0; i < (1 << N); i++) {
  265.         cout << i << " " << cache[i] << endl;
  266.     }
  267.  
  268.     PRN(ans);
  269.     return 0;
  270. }
Success #stdin #stdout 0s 5852KB
comments (?)
stdin
copy 
6
0.0 0.9 0.1 0.1 0.1 0.1
0.1 0.0 0.93 0.5 0.91 0.5
0.9 0.07 0.0 0.99 0.5 0.5
0.9 0.5 0.01 0.0 0.5 0.5
0.9 0.09 0.5 0.5 0.0 0.97
0.9 0.5 0.5 0.5 0.03 0.0
stdout
copy 
for mask 33: 1 6
for mask 17: 1 5
for mask 49: 5 6
for mask 9: 1 4
for mask 41: 4 6
for mask 25: 4 5
for mask 57: 4 5
for mask 5: 1 3
for mask 37: 3 6
for mask 21: 3 5
for mask 53: 3 5
for mask 13: 3 4
for mask 45: 3 4
for mask 29: 3 4
for mask 61: 3 4
for mask 3: 1 2
for mask 35: 6 2
for mask 19: 2 5
for mask 51: 6 5
for mask 11: 4 2
for mask 43: 4 6
for mask 27: 4 5
for mask 59: 4 6
for mask 7: 2 3
for mask 39: 3 6
for mask 23: 3 5
for mask 55: 6 5
for mask 15: 3 4
for mask 47: 4 6
for mask 31: 4 5
for mask 63: 5 6
0 0
1 0
2 0
3 0.9
4 0
5 0.1
6 0
7 0.844
8 0
9 0.1
10 0
11 0.5
12 0
13 0.1
14 0
15 0.84056
16 0
17 0.1
18 0
19 0.828
20 0
21 0.1
22 0
23 0.836
24 0
25 0.1
26 0
27 0.664
28 0
29 0.1
30 0
31 0.83828
32 0
33 0.1
34 0
35 0.5
36 0
37 0.1
38 0
39 0.672
40 0
41 0.1
42 0
43 0.5
44 0
45 0.1
46 0
47 0.75628
48 0
49 0.1
50 0
51 0.81816
52 0
53 0.1
54 0
55 0.83108
56 0
57 0.1
58 0
59 0.74108
60 0
61 0.1
62 0
63 0.83582
0.8358200000
https://ideone.com/QYmfXx
language:
C++14 (gcc 8.3)
created:
7 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!