Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. #define mp make_pair
  6. #define pub push_back
  7. #define x first
  8. #define y second
  9. #define all(a) a.begin(), a.end()
  10. #define db double
  11.  
  12. int a[6][6];
  13. int dp[1 << 6][1 << 6];
  14.  
  15. pair<int, int> getMove(int mask1, int mask2, int w1, int w2){
  16. mask1 ^= (1 << w1);
  17. mask2 ^= (1 << w2);
  18. if (w1 != w2){
  19. if (a[w1][w2] == w1){
  20. mask2 ^= (1 << w2);
  21. } else {
  22. mask1 ^= (1 << w1);
  23. }
  24. }
  25. return mp(mask1, mask2);
  26. }
  27.  
  28. int calc(int mask1, int mask2){
  29. if (dp[mask1][mask2] != -2) return dp[mask1][mask2];
  30. if (__builtin_popcount(mask2) == 0) return 6;
  31. if (__builtin_popcount(mask1) == 0) return -1;
  32. dp[mask1][mask2] = -1;
  33.  
  34. for (int i = 0; i < 6; i++) if ((mask1 >> i) & 1){
  35. bool ok = 1;
  36.  
  37. for (int j = 0; j < 6; j++) if ((mask2 >> j) & 1){
  38. auto now = getMove(mask1, mask2, i, j);
  39. int val = calc(now.x, now.y);
  40. if (val == -1){
  41. ok = 0;
  42. break;
  43. }
  44. }
  45.  
  46. if (ok){
  47. dp[mask1][mask2] = i;
  48. break;
  49. }
  50. }
  51.  
  52. return dp[mask1][mask2];
  53. }
  54.  
  55. pair<db, int> gg[64][64];
  56.  
  57. pair<db, int> calcProb(int mask1, int mask2){
  58. if (gg[mask1][mask2] != mp((db)-228, -228)) return gg[mask1][mask2];
  59. if (__builtin_popcount(mask2) == 0) return mp(1, -1);
  60. if (__builtin_popcount(mask1) == 0) return mp(0, -1);
  61.  
  62. pair<db, int> ans = mp(-1, -1);
  63.  
  64. for (int i = 0; i < 6; i++) if ((mask1 >> i) & 1){
  65. db sum = 0;
  66. for (int j = 0; j < 6; j++) if ((mask2 >> j) & 1){
  67. auto now = getMove(mask1, mask2, i, j);
  68. auto val = calcProb(now.x, now.y);
  69. sum += val.x / (db)__builtin_popcount(mask2);
  70. }
  71. if (sum > ans.x){
  72. ans = mp(sum, i);
  73. }
  74. }
  75. return gg[mask1][mask2] = ans;
  76. }
  77.  
  78. int makeMove(int mask1, int mask2){
  79. if (calc(mask1, mask2) != -1) return calc(mask1, mask2);
  80. return calcProb(mask1, mask2).y;
  81. }
  82.  
  83. int mask1, mask2;
  84.  
  85. int main(){
  86. srand(time(NULL));
  87. //freopen("input.txt", "r", stdin);
  88. //freopen("output2.txt", "w", stdout);
  89. ios_base::sync_with_stdio(0); cin.tie(0);
  90. int it = 5000;
  91. while(it--){
  92. for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) cin >> a[i][j];
  93. mask1 = (1 << 6) - 1, mask2 = (1 << 6) - 1;
  94. for (int i = 0; i < 64; i++) for (int j = 0; j < 64; j++) dp[i][j] = -2, gg[i][j] = mp(-228, -228);
  95. while(1){
  96.  
  97. int x = makeMove(mask1, mask2);
  98. cout << x << endl;
  99. int y;
  100. cin >> y;
  101.  
  102. auto now = getMove(mask1, mask2, x, y);
  103. mask1 = now.x;
  104. mask2 = now.y;
  105. if (min(__builtin_popcount(mask1), __builtin_popcount(mask2)) == 0){
  106. int x;
  107. cin >> x;
  108. break;
  109. }
  110. }
  111. }
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement