-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_cuttingbrownies.cpp
135 lines (126 loc) · 4.57 KB
/
kattis_cuttingbrownies.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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**Kattis - cuttingbrownies
* The optimal move for Harry is to cut the thinest piece at the middle (as middle as possible).
* Similarly, the optimal move is for Vicky to cut the shortest piece at the middle.
* We use a multiset to stare the remaining pieces. We use 2 multisets that allow us to get the
* shortest and the thinnest pieces in O(log n) time. Since we cannot split a piece of length 1
* horizontally or a piece of height 1 vertically, we encode this as buffer values hbuf and vbuf.
* I.e. hbuf is how many extra cuts that Harry can do without changing the pieces in the multisets,
* and vbuf is the same for Vicky. With this state representation, we need to note the edge cases
* when the input is of length or width 1.
*
* Time: O(hw log (hw)), Space: O(hw)
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int n, h, w;
multiset<pair<int, int>> hor, ver;
// hor: (x, y) allows us to find the thinest possible to cut horizontally
// ver: (y, x) allows us to find the shortest possible to cut vertically
int main()
{
int tc;
cin >> tc;
while (tc--) {
cin >> w >> h;
hor.clear();
ver.clear();
hor.insert({w, h});
ver.insert({h, w});
int hbuf = 0, vbuf = 0;
string starter;
cin >> starter;
int horPlayer = starter == "Harry" ? 1 : 0;
int winningPlayer = 0;
int startPlayer = horPlayer;
if (w == 1 && h == 1) {
cout << starter << " cannot win\n";
continue;
}
else if (w == 1) {
// so we can only cut horizontally
winningPlayer = 1;
}
else if (h == 1) {
// so we can only cut vertically
winningPlayer = 0;
}
else {
while (!hor.empty()) {
assert(hor.size() == ver.size());
if (horPlayer) {
if (hbuf) {
hbuf--;
horPlayer = 1 - horPlayer;
continue;
}
// cur horizontally
auto [x, y] = *hor.begin();
hor.erase(hor.begin());
ver.erase(ver.find({y, x}));
// cut as in the middle as possible
assert(y >= 2);
int mid = y / 2;
if (mid == 1) {
vbuf += x - 1;
}
else {
hor.insert({x, mid});
ver.insert({mid, x});
}
if (y - mid == 1) {
vbuf += x - 1;
}
else {
hor.insert({x, y - mid});
ver.insert({y - mid, x});
}
}
else {
if (vbuf) {
vbuf--;
horPlayer = 1 - horPlayer;
continue;
}
// cur vertically
auto [y, x] = *ver.begin();
hor.erase(hor.find({x, y}));
ver.erase(ver.begin());
// cut as in the middle as possible
assert(x >= 2);
int mid = x / 2;
if (mid == 1) {
hbuf += y - 1;
}
else {
hor.insert({mid, y});
ver.insert({y, mid});
}
if (x - mid == 1) {
hbuf += y - 1;
}
else {
hor.insert({x - mid, y});
ver.insert({y, x - mid});
}
}
horPlayer = 1 - horPlayer;
}
winningPlayer = 1 - horPlayer; // the one who doesn't need to move
}
assert(min(hbuf, vbuf) == 0); // only 1 can be positive
if (hbuf > 0) {
winningPlayer = 1;
}
else if (vbuf > 0) {
winningPlayer = 0;
}
if (winningPlayer != startPlayer)
cout << starter << " cannot win\n";
else
cout << starter << " can win\n";
}
return 0;
}