SHARE
TWEET

Untitled

a guest Apr 21st, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <functional>
  4. #include <iostream>
  5. #include <string>
  6.  
  7. #include <chrono>
  8.  
  9. using namespace std;
  10.  
  11. template<size_t disk>
  12. void fill(bitset<disk>& state, const string& input) {
  13.   auto size = input.size();
  14.   for (size_t i = 0; i < size; i++) {
  15.     state[i] = input[i] == '1';
  16.   }
  17.   while (size < disk) {
  18.     for (size_t i = 0; i < size && size + 1 + i < disk; i++) {
  19.       state[size + 1 + i] = !state[size - 1 - i];
  20.     }
  21.     size += size + 1;
  22.   }
  23. }
  24.  
  25. template<size_t disk>
  26. string checksum(bitset<disk>& state) {
  27.   auto size = state.size();
  28.   while (size % 2 == 0) {
  29.     if (size % 4 == 0) {
  30.       size /= 4;
  31.       for (size_t i = 0; i < size; i++) {
  32.         state[i] = (state[i * 4] == state[i * 4 + 1]) == (state[i * 4 + 2] == state[i * 4 + 3]);
  33.       }
  34.     } else {
  35.       size /= 2;
  36.       for (size_t i = 0; i < size; i++) {
  37.         state[i] = state[i * 2] == state[i * 2 + 1];
  38.       }
  39.     }
  40.   }
  41.   string answer;
  42.   for (size_t i = 0; i < size; i++) {
  43.     answer += state[i] ? '1' : '0';
  44.   }
  45.   return answer;
  46. }
  47.  
  48. string part1(const string& input) {
  49.   static bitset<272> state;
  50.   fill(state, input);
  51.   return checksum(state);
  52. }
  53.  
  54. string part2(const string& input) {
  55.   static bitset<35651584> state;
  56.   fill(state, input);
  57.   return checksum(state);
  58. }
  59.  
  60. int main(int argc, char* argv[]) {
  61.   auto start = chrono::steady_clock::now();
  62.  
  63.   cout << part1("11011110011011101") << endl;
  64.   cout << part2("11011110011011101") << endl;
  65.  
  66.   auto end = chrono::steady_clock::now();
  67.   cout << "Time taken: "
  68.     << chrono::duration_cast<chrono::duration<double>>(end - start).count()
  69.     << "s" << endl;
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top