-
Notifications
You must be signed in to change notification settings - Fork 0
/
22.cpp
113 lines (92 loc) · 2.4 KB
/
22.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
// Uncomment for part 1
#define PART2 1
#define ul unsigned long long
static void print(const list<int> &l) {
for (auto i : l)
cout << i << " ";
cout << endl;
}
ul hashround(const list<int>& p1, const list<int>& p2) {
ul seed = p1.size();
for (auto i : p1) {
seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
seed += p2.size() * 100;
for (auto i : p2) {
seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
// (winnerdeck, p1wins)
pair<list<int>, bool> game(list<int> p1, list<int> p2) {
unordered_set<ul> rounds;
while (p1.size() != 0 && p2.size() != 0) {
#ifdef PART2
ul h = hashround(p1, p2);
// There is already a round like this
if (rounds.find(h) != rounds.end()) {
return { p1, true };
} else
rounds.insert(h);
#endif
int c1 = p1.front();
int c2 = p2.front();
p1.pop_front();
p2.pop_front();
bool p1wins;
#ifdef PART2
// We can launch a recursive game
if (p1.size() >= c1 && p2.size() >= c2) {
auto p1deck = list<int>();
auto p2deck = list<int>();
auto c1it = p1.begin();
auto c2it = p2.begin();
for (int i = 0; i < c1; ++i) {
p1deck.push_back(*c1it);
++c1it;
}
for (int i = 0; i < c2; ++i) {
p2deck.push_back(*c2it);
++c2it;
}
auto [winner, _p1wins] = game(p1deck, p2deck);
p1wins = _p1wins;
} else
#endif
p1wins = c1 > c2;
if (p1wins) {
p1.push_back(c1);
p1.push_back(c2);
} else {
p2.push_back(c2);
p2.push_back(c1);
}
}
return { !p1.size() ? p2 : p1, p1.size() != 0 };
}
int main() {
list<int> p1;
list<int> p2;
string line;
getline(cin, line);
while (getline(cin, line) && line != "")
p1.push_back(stoi(line));
getline(cin, line);
while (getline(cin, line))
p2.push_back(stoi(line));
auto [winner, p1wins] = game(p1, p2);
ul mul = winner.size();
ul total = 0;
for (auto i : winner) {
total += mul-- * i;
}
#ifdef PART2
cout << "Part 2 : "
#else
cout << "Part 1 : "
#endif
<< total << endl;
return 0;
}