#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <string>

#include <chrono>

using namespace std;

template<size_t disk>
void fill(bitset<disk>& state, const string& input) {
  auto size = input.size();
  for (size_t i = 0; i < size; i++) {
    state[i] = input[i] == '1';
  }
  while (size < disk) {
    for (size_t i = 0; i < size && size + 1 + i < disk; i++) {
      state[size + 1 + i] = !state[size - 1 - i];
    }
    size += size + 1;
  }
}

template<size_t disk>
string checksum(bitset<disk>& state) {
  auto size = state.size();
  while (size % 2 == 0) {
    if (size % 4 == 0) {
      size /= 4;
      for (size_t i = 0; i < size; i++) {
        state[i] = (state[i * 4] == state[i * 4 + 1]) == (state[i * 4 + 2] == state[i * 4 + 3]);
      }
    } else {
      size /= 2;
      for (size_t i = 0; i < size; i++) {
        state[i] = state[i * 2] == state[i * 2 + 1];
      }
    }
  }
  string answer;
  for (size_t i = 0; i < size; i++) {
    answer += state[i] ? '1' : '0';
  }
  return answer;
}

string part1(const string& input) {
  static bitset<272> state;
  fill(state, input);
  return checksum(state);
}

string part2(const string& input) {
  static bitset<35651584> state;
  fill(state, input);
  return checksum(state);
}

int main(int argc, char* argv[]) {
  auto start = chrono::steady_clock::now();

  cout << part1("11011110011011101") << endl;
  cout << part2("11011110011011101") << endl;

  auto end = chrono::steady_clock::now();
  cout << "Time taken: "
    << chrono::duration_cast<chrono::duration<double>>(end - start).count()
    << "s" << endl;
}