fork download 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16. using namespace std;
  17. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  18. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  19.   while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  20. }
  21. #ifdef LOCAL
  22. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  23. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  24. #else
  25. #define debug(...) (__VA_ARGS__)
  26. #define debugv(x)
  27. #define cerr if(0)cout
  28. #endif
  29. #define make(type, x) type x; cin>>x;
  30. #define make2(type, x, y) type x, y; cin>>x>>y;
  31. #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
  32. #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;
  33. #define next ____next
  34. #define prev ____prev
  35. #define left ____left
  36. #define hash ____hash
  37. typedef long long ll;
  38. typedef long double LD;
  39. typedef pair<int, int> PII;
  40. typedef pair<ll, ll> PLL;
  41. typedef vector<int> VI;
  42. typedef vector<VI> VVI;
  43. typedef vector<ll> VLL;
  44. typedef vector<pair<int, int> > VPII;
  45. typedef vector<pair<ll, ll> > VPLL;
  46.  
  47. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  48. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  49. template<class T1, class T2>
  50. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  51. template<class A, class B, class C> struct Triple { A first; B second; C third;
  52.   bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
  53. template<class T> void ResizeVec(T&, vector<int>) {}
  54. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  55.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  56.   for (T& v : vec) { ResizeVec(v, sz); }
  57. }
  58. typedef Triple<int, int, int> TIII;
  59. template<class A, class B, class C>
  60. ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
  61. template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  62.  
  63. const int N = 12;
  64. const int R = 112;
  65. int dice[N][N];
  66. LD dp[1 << N];
  67. int fir[1 << N];
  68. int order[N];
  69. bool accept_sub[1 << N][N][N];
  70. bool accept[N][R];
  71. LD cdf[R];
  72. int valid[R];
  73. const LD kEps = 1e-9;
  74. void RecomputeDp(int n) {
  75.   dp[0] = -1;
  76.   for (int mask = 2; mask < (2 << n); mask += 2) {
  77.     int pop = __builtin_popcount(mask);
  78.     dp[mask] = -1;
  79.     RE (bit, n) {
  80.       if (mask & (1 << bit)) {
  81.         int prev = mask - (1 << bit);
  82.         LD res = 0;
  83.         REP (side, 6) {
  84.           if (dp[prev] > cdf[dice[bit][side] + pop]) {
  85.             accept_sub[mask][bit][side] = 0;
  86.           } else {
  87.             accept_sub[mask][bit][side] = 1;
  88.           }
  89.           res += max(dp[prev], cdf[dice[bit][side] + pop]);
  90.         }
  91.         res /= 6;
  92.         debug(bit, res);
  93.         if (res > dp[mask]) {
  94.           fir[mask] = bit;
  95.           dp[mask] = res;
  96.         }
  97.       }
  98.     }
  99.     debug(mask, dp[mask]);
  100.   }
  101.  
  102.   int full_mask = (2 << n) - 2;
  103.   int cnt = 0;
  104.   while (full_mask) {
  105.     cnt++;
  106.     int ziom = fir[full_mask];
  107.     debug(cnt, ziom);
  108.     order[cnt] = ziom;
  109.     REP (side, 6) {
  110.       accept[ziom][dice[ziom][side]] = accept_sub[full_mask][ziom][side];
  111.     }
  112.     full_mask -= (1 << ziom);
  113.   }
  114. }
  115. LD wins[R];
  116. LD mult[R];
  117. void RecomputeCdf(int turns) {
  118.   cdf[R - 1] = 1;
  119.   VPII mults;
  120.   REP (i, R) {
  121.     mults.PB({mult[i], i});
  122.   }
  123.   sort(ALL(mults), greater<PII>());
  124.   int DUPA = 16;
  125.   while (SZ(mults) > DUPA || mults.back().st < mults[0].st / 4) { mults.pop_back(); }
  126.   vector<LD> vals;
  127.   VI wazni_panowie;
  128.   int gowno = 0;
  129.   for (auto p : mults) {
  130.     wazni_panowie.PB(p.nd);
  131.     if (p.st == 0) {
  132.       vals.PB(54654);
  133.     } else {
  134.       vals.PB(wins[p.nd] / p.st + gowno / 1e6);
  135.     }
  136.     gowno++;
  137.   }
  138.   vals.PB(0);
  139.   wazni_panowie.PB(0);
  140.   vals.PB(1);
  141.   wazni_panowie.PB(R - 1);
  142.   sort(ALL(wazni_panowie));
  143.   sort(ALL(vals));
  144.  
  145.   debug(vals);
  146.   debug(wazni_panowie);
  147.   for (int i = 0; i < SZ(wazni_panowie) - 1; i++) {
  148.     FOR (j, wazni_panowie[i], wazni_panowie[i + 1] - 1) {
  149.       cdf[j] = ((j - wazni_panowie[i]) * vals[i + 1] + (wazni_panowie[i + 1] - j) * vals[i]) / (wazni_panowie[i + 1] - wazni_panowie[i]);
  150.     }
  151.   }
  152.   REP (i, R) {
  153.     debug(cdf[i]);
  154.   }
  155. }
  156. const int kIter = 10000;
  157. #ifdef LOCAL
  158. const int kPeriod = 1;
  159. #else
  160. const int kPeriod = 12;
  161. #endif
  162. #undef int
  163. int main() {
  164. #define int long long
  165.  
  166.   int n;
  167.   cin>>n;
  168.   RE (i, n) {
  169.     REP (side, 6) {
  170.       cin>>dice[i][side];
  171.     }
  172.   }
  173.   int won = 0;
  174.   mult[0] = 1;
  175.   wins[R - 1] = 1;
  176.   mult[R - 1] = 1;
  177.   REP (iter, kIter) {
  178.     if (iter % kPeriod == 0) {
  179.       if (iter) { RecomputeCdf(iter); }
  180.       RecomputeDp(n);
  181.     }
  182.     int sc = 0;
  183.     RE (i, n) {
  184.       cout<<order[i]<<endl;
  185.       int res;
  186.       cin>>res;
  187.       res += i - 1;
  188.       if (accept[order[i]][res]) {
  189.         cout<<"Yes"<<endl;
  190.         sc = res + n - i + 1;
  191.         break;
  192.       } else {
  193.         cout<<"No"<<endl;
  194.       }
  195.     }
  196.     string hehs;
  197.     cin>>hehs;
  198.     if (hehs == "Win") {
  199.       wins[sc]++;
  200.       won++;
  201.     }
  202.     mult[sc]++;
  203.   }
  204.  
  205.  
  206.  
  207.  
  208.   return 0;
  209. }
  210.  
Success #stdin #stdout 0.01s 4088KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SsFW3X
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!