2024/09/day09a.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <string_view>
#include <vector>
using namespace std;

int main() {
	vector<long long> a;
	char c;
	for (int id = 0; cin >> c; id++)
		for (int j = 0; j < c-'0'; j++)
			a.push_back(id % 2 == 0 ? id/2 : -1); // -1 = space

	int j = 0;
	for (int i = a.size()-1; i >= 0; i--) {
		while (a[j] >= 0) j++;
		if (a[j] == -2) break;
		a[j] = a[i];
		a[i] = -2; // -2 = freed up
	}

	long long checksum = 0;
	for (long long i = 0; i < (long long)a.size() && a[i] != -2; i++)
		checksum += i*a[i];
	cout << checksum << endl;

	return 0;
}