Branch data     Line data    Source code

       1                 :             : #include <algorithm>
       2                 :             : #include <cstdint>
       3                 :             : #include <fstream>
       4                 :             : #include <iostream>
       5                 :             : #include <numeric>
       6                 :             : #include <utility>
       7                 :             : #include <vector>
       8                 :             : #include <array>
       9                 :             : using namespace std;
      10                 :             : 
      11                 :             : constexpr array<uint64_t, 20> POW10{
      12                 :             :   1ULL, 10ULL, 100ULL, 1000ULL, 10000ULL, 100000ULL, 1000000ULL, 10000000ULL,
      13                 :             :   100000000ULL, 1000000000ULL, 10000000000ULL, 100000000000ULL,
      14                 :             :   1000000000000ULL, 10000000000000ULL, 100000000000000ULL, 1000000000000000ULL,
      15                 :             :   10000000000000000ULL, 100000000000000000ULL, 1000000000000000000ULL,
      16                 :             :   10000000000000000000ULL
      17                 :             : };
      18                 :             : 
      19                 :             : struct Node {
      20                 :             :   uint64_t stone;
      21                 :             :   uint64_t count;
      22                 :             : };
      23                 :             : 
      24                 :          75 : void sort_and_merge(vector<Node>& v) {
      25                 :          75 :   ranges::sort(v, [](const Node& a, const Node& b) {
      26                 :     2475195 :     return a.stone < b.stone;
      27                 :             :   });
      28                 :          75 :   size_t w = 0;
      29         [ +  + ]:      119954 :   for (size_t i = 0; i < v.size(); ) {
      30                 :      119879 :     const uint64_t stone = v[i].stone;
      31                 :      119879 :     uint64_t total = 0;
      32                 :             :     do {
      33                 :      183516 :       total += v[i].count; ++i;
      34   [ +  +  +  +  :      183516 :     } while (i < v.size() && v[i].stone == stone);
                   +  + ]
      35                 :      119879 :     v[w++] = {stone, total};
      36                 :             :   }
      37                 :          75 :   v.resize(w);
      38                 :          75 : }
      39                 :             : 
      40                 :           2 : int main() {
      41                 :           2 :   ifstream inputFile("input.txt");
      42         [ +  + ]:           2 :   if (!inputFile) {
      43                 :           1 :     cerr << "Error: input.txt not found or inaccessible." << endl;
      44                 :           1 :     return 1;
      45                 :             :   }
      46                 :             : 
      47                 :           1 :   vector<Node> stones;
      48                 :           1 :   vector<Node> next;
      49         [ +  + ]:           9 :   for (uint64_t num; inputFile >> num; stones.emplace_back(num, 1)); // Read input stones as (stone,1),
      50                 :             : 
      51                 :           1 :   uint_fast8_t blinks = 75;
      52         [ +  + ]:          76 :   while (blinks--) {
      53                 :          75 :     next.clear();
      54                 :             : 
      55         [ +  + ]:      116228 :     for (const auto& [stone, count] : stones) {
      56         [ +  + ]:      116153 :       if (stone == 0) {
      57                 :          71 :         next.emplace_back(1ULL, count);
      58                 :             :       } else {
      59                 :      116082 :         uint_fast8_t d = 1;
      60         [ +  + ]:      668733 :         for (; stone >= POW10[d]; ++d);
      61         [ +  + ]:      116082 :         if ((d & 1) == 0) {
      62                 :       67363 :           const uint64_t div = POW10[d / 2];
      63                 :       67363 :           const uint64_t left  = stone / div;
      64                 :       67363 :           const uint64_t right = stone % div;
      65                 :       67363 :           next.emplace_back(left,  count);
      66                 :       67363 :           next.emplace_back(right, count);
      67                 :             :         } else {
      68                 :       48719 :           next.emplace_back(stone * 2024ULL, count);
      69                 :             :         }
      70                 :             :       }
      71                 :             :     }
      72                 :          75 :     sort_and_merge(next); // Sort by stone and merge counts of equal stones.
      73                 :          75 :     stones.swap(next);
      74                 :             :   }
      75                 :             : 
      76                 :        3735 :   cout << accumulate(stones.begin(), stones.end(), 0ULL, [](uint64_t sum, const auto& e) { return sum + e.count; }) << endl;
      77         [ +  + ]:           3 : }