Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <vector>
       4                 :             : #include <tuple>
       5                 :             : #include <deque>
       6                 :             : #include <string>
       7                 :             : using namespace std;
       8                 :             : 
       9                 :           2 : int main() {
      10                 :           2 :   ifstream inputFile("input.txt");
      11                 :           2 :   string line;
      12         [ +  + ]:           2 :   if (!getline(inputFile, line)) {
      13                 :           1 :     cerr << "Error opening/reading file." << endl;
      14                 :           1 :     return 1;
      15                 :             :   }
      16                 :             : 
      17                 :           1 :   long long checksum = 0;
      18                 :           1 :   long long start = 0;
      19                 :           1 :   vector<tuple<long long, int, int>> disk; // start, size, index
      20                 :           1 :   deque<int> freeBlocks; // indices of free blocks
      21                 :             : 
      22         [ +  + ]:       20000 :   for (int id = 0, i = 0, len; i < (int)line.size(); start += len, ++i) {
      23                 :       19999 :         len = line[i] - '0';
      24         [ +  + ]:       19999 :     if (!(i & 1)) {
      25                 :       10000 :       checksum += id * start * len + id * len * (len - 1) / 2;
      26                 :             :     } else {
      27                 :        9999 :       freeBlocks.push_back((int)disk.size());
      28                 :             :     }
      29         [ +  + ]:       19999 :     disk.emplace_back(start, len, i & 1 ? -1 : id++);
      30                 :             :   }
      31                 :             : 
      32         [ +  + ]:       19999 :   for (int usedIdx = (int)disk.size() - 1; usedIdx >= 1; --usedIdx) {
      33         [ +  + ]:       19998 :     if (get<2>(disk[usedIdx]) != -1) {
      34         [ +  - ]:     3802521 :       for (auto it = freeBlocks.begin(); it != freeBlocks.end(); ++it) {
      35                 :     3802521 :         int freeIdx = *it;
      36         [ +  + ]:     3802521 :         if (freeIdx >= usedIdx) {
      37                 :        5050 :           break;
      38                 :             :         }
      39         [ +  + ]:     3797471 :         if (get<1>(disk[freeIdx]) >= get<1>(disk[usedIdx])) {
      40                 :        4949 :           int diff = get<1>(disk[usedIdx]);
      41                 :        4949 :           checksum += get<2>(disk[usedIdx]) * diff * (get<0>(disk[freeIdx]) - get<0>(disk[usedIdx]));
      42                 :        4949 :           get<1>(disk[freeIdx]) -= diff;
      43                 :        4949 :           get<0>(disk[freeIdx]) += diff;
      44                 :             : 
      45         [ +  + ]:        4949 :           if (get<1>(disk[freeIdx]) == 0) {
      46                 :        4476 :             freeBlocks.erase(it);
      47                 :             :           }
      48                 :        4949 :           break;
      49                 :             :         }
      50                 :             :       }
      51                 :             :     }
      52                 :             :   }
      53                 :             : 
      54                 :           1 :   cout << checksum << endl;
      55   [ +  +  +  + ]:           4 : }