Google Code Jam 2022 Round1B - ASeDatAb

main.cpp

#include <bits/stdc++.h>
#include <random>
using namespace std;

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#define itrout(x) for(int i=0;i<x.size();i++) {cout << x[i] << (i==x.size()-1 ? "\n" : " ");}
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define debugbit(x, n) cerr << #x << " = " << bitset<n>(x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) cerr << #x << " "; for (auto & el : (x)) {cerr << (el) << " ";} cerr << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define debug(x)
#define debugbit(x, n)
#define itrdebug(x)
#define dassert(...)
#endif
#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

signed main(){
    auto rotate = [](int x, int r /* rotate to right */) {
        return (x >> r | x << (8 - r)) & ((1<<8) - 1);
    };
    vector<int> toPopCnt(1<<8, 0);
    rep(i,0,1<<8) rep(j,0,8) if (i & (1<<j)) toPopCnt[i]++;
    vector<vector<int>> patternByPopCnt(9);
    unordered_set<int> patterns; // base patterns(records)
    vector<int> toBasePatterns(1<<8);
    rep(i,0,1<<8) {
        bool valid = true;
        rep(j,0,8) {
            int rotated = rotate(i, j);
            if (patterns.find(rotated) != patterns.end()) {
                valid = false;
                toBasePatterns[i] = rotated;
                break;
            }
        }
        if (!valid) continue;
        toBasePatterns[i] = i;
        int cnt = 0;
        rep(j,0,8) if (i & (1<<j)) cnt++;
        patterns.insert(i);
        patternByPopCnt[cnt].push_back(i);
    }
    vector<vector<bool>> processed(9, vector<bool>(1<<10, false));
    auto getState = [&](int popCnt, unordered_set<int> possiblePatterns) -> int {
        int state = 0;
        rep(i,0,patternByPopCnt[popCnt].size()) {
            if (possiblePatterns.find(patternByPopCnt[popCnt][i]) != possiblePatterns.end()) {
                state |= 1<<i;
            }
        }
        return state;
    };
    processed[0][getState(0, {0})] = true; // initial state
    vector<vector<int>> toZero(9, vector<int>(1<<10, -1));
    vector<vector<unordered_map<int, unordered_map<int, int>>>> toState(9, vector<unordered_map<int, unordered_map<int, int>>>(9));
    int processedCnt = 0;
    while (true) {
        vector<vector<int>> adds(9);
        rep(popCnt,0,9) { // pop count of source state
            rep(sourceState,1,1<<patternByPopCnt[popCnt].size()) { // A
                if (processed[popCnt][sourceState]) continue;
                for (auto inputPattern : patterns) { // V
                    bool valid = true;
                    vector<unordered_set<int>> possibleDestPatterns(9);
                    rep(i,0,patternByPopCnt[popCnt].size()) {
                        if (!(sourceState & (1<<i))) continue;
                        int sourcePattern = patternByPopCnt[popCnt][i];
                        rep(r,0,8) {
                            int destPattern = toBasePatterns[sourcePattern ^ rotate(inputPattern, r)];
                            possibleDestPatterns[toPopCnt[destPattern]].insert(destPattern);
                        }
                    }
                    rep(i,0,9) {
                        if (possibleDestPatterns[i].empty()) continue;
                        int destState = getState(i, possibleDestPatterns[i]);
                        toState[popCnt][i][sourceState][inputPattern] = destState;
                        if (!processed[i][destState]) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) {
                        adds[popCnt].push_back(sourceState);
                        toZero[popCnt][sourceState] = inputPattern;
                        processedCnt++;
                        debug(processedCnt);
                    }
                }
            }
        }
        bool allProcessed = true;
        rep(popCnt, 0, 9) {
            for (auto add : adds[popCnt]) {
                allProcessed = false;
                processed[popCnt][add] = true;
            }
        }
        if (allProcessed) break;
    }
    int T;
    cin >> T;
    rep(ti,1,T+1) {
        int res, prev;
        cout << bitset<8>(0) << endl;
        cin >> res;
        int currentState = (1<<(patternByPopCnt[res].size())) - 1; // all patterns are possible.
        while (res > 0) {
            prev = res;
            int inputPattern = toZero[res][currentState];
            cout << bitset<8>(inputPattern) << endl;
            cin >> res;
            currentState = toState[prev][res][currentState][inputPattern];
        }
        assert(res != -1);
    }
}