CH0104 起床困难综合症

#include <iostream>
#include <cstring>
#define x first
#define y second
using PSI = std::pair<std::string, int>;

const int N = 1e5 + 10;

int n, m, t, ans;
std::string op;
PSI ops[N];

template <class T>
T calc(const T& a, const std::string& op, const T& b) {
    if(op == "AND") return a & b;
    else if(op == "OR") return a | b;
    else if(op == "XOR") return a ^ b;
    std::cout << "Error\n";
    return -1;
}

int breakThrough(int a, int idx) {
    for(int i = 0; i < n; ++i) {
        std::string op = ops[i].x;
        int b = ops[i].y >> idx & 1;
        a = calc<int>(a, op, b);
    }
    return a;
}

int main () {
    std::cin >> n >> m;

    for(int i = 0; i < n; ++i) {
        std::cin >> op >> t;
        ops[i] = {op, t};
    }

    bool less = 0;
    for(int i = 30; i >= 0; --i) {
        int input = m >> i & 1;
        bool isZero = !input;
        int output1 = breakThrough(input, i);
        int output2 = breakThrough(!input, i);
        // 有 16 种组合
        if(isZero) {
            if(less) {
                if(output1) {
                    if(output2) { // [1] 前缀已小于m，低位可自由选择，实际输入为 0 情况下输出为 1，输入为 1 的情况下输出为 1
                        ans += 1 << i;
                    }
                    else { // [2] 前缀已小于m，低位可自由选择，实际输入为 0 情况下输出为 1，输入为 1 的情况下输出为 0
                        ans += 1 << i;
                    }
                }
                else {
                    if(output2) { // [3] 前缀已小于m，低位可自由选择，实际输入为 0 情况下输出为 0，如果输入为 1 情况下输出 1
                        ans += 1 << i;
                    }
                    else { // [4] 前缀已小于m，低位可自由选择，实际输入为 0 情况下输出为 0，如果输入为 1 情况下输出 0

                    }
                }
            }
            else {
                if(output1) {
                    if(output2) { // [5] 前缀仍等于 m，当前位受上界约束，实际输入为 0 情况下输出为 1，输入为 1 的情况下输出为 1
                        ans += 1 << i;
                    }
                    else { // [6] 前缀仍等于 m，当前位受上界约束，实际输入为 0 情况下输出为 1，输入为 1 的情况下输出为 0
                        ans += 1 << i;
                    }
                }
                else {
                    if(output2) { // [7] 前缀仍等于 m，当前位受上界约束，实际输入为 0 情况下输出为 0，如果输入为 1 情况下输出 1
                        
                    }
                    else { // [8] 前缀仍等于 m，当前位受上界约束，实际输入为 0 情况下输出为 0，如果输入为 1 情况下输出 0

                    }
                }
            }
        }
        else {
            if(less) {
                if(output1) {
                    if(output2) { // [9] 前缀已小于m，低位可自由选择，实际输入为 1 情况下输出为 1，输入为 0 的情况下输出为 1
                        less = 1;
                        ans += 1 << i;
                    }
                    else { // [10] 前缀已小于m，低位可自由选择，实际输入为 1 情况下输出为 1，输入为 0 的情况下输出为 0
                        ans += 1 << i;
                    }
                }
                else {
                    if(output2) { // [11] 前缀已小于m，低位可自由选择，实际输入为 1 情况下输出为 0，如果输入为 0 情况下输出 1
                        ans += 1 << i;
                    }
                    else { // [12] 前缀已小于m，低位可自由选择，实际输入为 1 情况下输出为 0，如果输入为 0 情况下输出 0

                    }
                }
            }
            else {
                if(output1) { 
                    if(output2) { // [13] 前缀仍等于 m，当前位受上界约束，实际输入为 1 情况下输出为 1，输入为 0 的情况下输出为 1
                        less = 1;
                        ans += 1 << i;
                    }
                    else { // [14] 前缀仍等于 m，当前位受上界约束，实际输入为 1 情况下输出为 1，输入为 0 的情况下输出为 0
                        ans += 1 << i;
                    }
                }
                else {
                    if(output2) { // [15] 前缀仍等于 m，当前位受上界约束，实际输入为 1 情况下输出为 0，如果输入为 0 情况下输出 1
                        less = 1;
                        ans += 1 << i;
                    }
                    else { // [16] 前缀仍等于 m，当前位受上界约束，实际输入为 1 情况下输出为 0，如果输入为 0 情况下输出 0
                        less = 1;
                    }
                }
            }
        }
    }

    std::cout << ans;

    return 0;
}