Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define mp make_pair
- #define pub push_back
- #define x first
- #define y second
- #define all(a) a.begin(), a.end()
- #define db double
- int a[6][6];
- int dp[1 << 6][1 << 6];
- pair<int, int> getMove(int mask1, int mask2, int w1, int w2){
- mask1 ^= (1 << w1);
- mask2 ^= (1 << w2);
- if (w1 != w2){
- if (a[w1][w2] == w1){
- mask2 ^= (1 << w2);
- } else {
- mask1 ^= (1 << w1);
- }
- }
- return mp(mask1, mask2);
- }
- int calc(int mask1, int mask2){
- if (dp[mask1][mask2] != -2) return dp[mask1][mask2];
- if (__builtin_popcount(mask2) == 0) return 6;
- if (__builtin_popcount(mask1) == 0) return -1;
- dp[mask1][mask2] = -1;
- for (int i = 0; i < 6; i++) if ((mask1 >> i) & 1){
- bool ok = 1;
- for (int j = 0; j < 6; j++) if ((mask2 >> j) & 1){
- auto now = getMove(mask1, mask2, i, j);
- int val = calc(now.x, now.y);
- if (val == -1){
- ok = 0;
- break;
- }
- }
- if (ok){
- dp[mask1][mask2] = i;
- break;
- }
- }
- return dp[mask1][mask2];
- }
- pair<db, int> gg[64][64];
- pair<db, int> calcProb(int mask1, int mask2){
- if (gg[mask1][mask2] != mp((db)-228, -228)) return gg[mask1][mask2];
- if (__builtin_popcount(mask2) == 0) return mp(1, -1);
- if (__builtin_popcount(mask1) == 0) return mp(0, -1);
- pair<db, int> ans = mp(-1, -1);
- for (int i = 0; i < 6; i++) if ((mask1 >> i) & 1){
- db sum = 0;
- for (int j = 0; j < 6; j++) if ((mask2 >> j) & 1){
- auto now = getMove(mask1, mask2, i, j);
- auto val = calcProb(now.x, now.y);
- sum += val.x / (db)__builtin_popcount(mask2);
- }
- if (sum > ans.x){
- ans = mp(sum, i);
- }
- }
- return gg[mask1][mask2] = ans;
- }
- int makeMove(int mask1, int mask2){
- if (calc(mask1, mask2) != -1) return calc(mask1, mask2);
- return calcProb(mask1, mask2).y;
- }
- int mask1, mask2;
- int main(){
- srand(time(NULL));
- //freopen("input.txt", "r", stdin);
- //freopen("output2.txt", "w", stdout);
- ios_base::sync_with_stdio(0); cin.tie(0);
- int it = 5000;
- while(it--){
- for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) cin >> a[i][j];
- mask1 = (1 << 6) - 1, mask2 = (1 << 6) - 1;
- for (int i = 0; i < 64; i++) for (int j = 0; j < 64; j++) dp[i][j] = -2, gg[i][j] = mp(-228, -228);
- while(1){
- int x = makeMove(mask1, mask2);
- cout << x << endl;
- int y;
- cin >> y;
- auto now = getMove(mask1, mask2, x, y);
- mask1 = now.x;
- mask2 = now.y;
- if (min(__builtin_popcount(mask1), __builtin_popcount(mask2)) == 0){
- int x;
- cin >> x;
- break;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement