# # UOJ002 - Hard to Get Up

Submit Your Solution (opens new window)

TIP

This problem is from NOI 2014.

## # Description

A warrior is to slay an evil dragon which hinders people from getting up easily. The dragon has $n$ gates defending it from attacks. On each gate there is an operation $op$ and a parameter $t$. $op$ can be $\text{OR}$, $\text{XOR}$ or $\text{AND}$，while $t$ is a non-negative integer.

The warrior needs to pass the gates one by one. If his attack power is $x$ before passing the gate, then his attack damage becomes $x\ op\ t$ after passing it. The damage taken by the dragon is the final result after all $m$ operations.

The warrior can freely choose his attack power from $[0,m]$, which must be an integer. However, the intermediate results and the final damage can be larger than $m$. Please help the warrior calculate the highest damage he can make if he chooses his attack power optimally.

## # Input

In the first line, there are two integers $n$ ($2\leq n\leq10^5$) and $m$ ($2\leq m<2^{30}$), representing the number of gates and the upper bound of the warrior's attack power.

The following $n$ lines each contain a string $op$ and a non-negative integer $t$ ($0\leq t<2^{30}$) separated by a whitespace. $op$ is one of $\text{OR}$, $\text{XOR}$ or $\text{AND}$, and $t$ is the corresponding parameter.

## # Output

An integer, the highest damage the warrior can make.

## # Samples

### # Input 1

3 10
AND 5
OR 6
XOR 7

1
2
3
4

### # Output 1

1

1

### # Sample Explanation

If the warrior chooses $4$ as his initial attack power, then we have

\begin{aligned} 4\text{ AND }5=4 \\ 4\text{ OR }6=6 \\ 6\text{ XOR }7=1 \end{aligned}

So the final damage is $1$.

Similarly, we can calculate that the final damage is $0$ if the initial attack power is $1,3,5,7,9$ and $1$ if the initial attack power is $0,2,4,6,8,10$. So the highest damage the warrior can make is $10$.

## # Tutorial

Hint 1

Consider each bit separately.

Hint 2

If for a set bit of $m$, it is not worse to choose $0$, we should choose $0$. More than that, we are free to choose from $0$ and $1$ for the bits following.

Code (C++)
#include <bitset>
#include <iostream>
#include <vector>

using namespace std;

inline int go(int x, int y, int op_type) {
switch (op_type) {
case 0:
return x | y;
case 1:
return x & y;
default:
return x ^ y;
}
}

int main() {
int n, m;
cin >> n >> m;
vector<int> op(n);
vector<bitset<32>> t(n);
for (int i = 0; i < n; ++i) {
string s;
int ti;
cin >> s >> ti;
t[i] = bitset<32>(ti);
if (s == "AND")
op[i] = 1;
else if (s == "XOR")
op[i] = 2;
}
int ans = 0;
for (int i = 29; i >= 0; --i) {
bool flag = m & (1 << i);
int zero = 0, one = 1;
for (int j = 0; j < n; ++j) {
zero = go(zero, t[j][i], op[j]);
one = go(one, t[j][i], op[j]);
}
one = one && flag;
if (flag && (zero || !one))
m = (1 << i) - 1;
if (zero || one)
ans += 1 << i;
}
cout << ans;
}

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