Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II

問題

codeforces.com

解法

まず ans = 1 のものを集めて範囲を絞ります。
その後に ans = 0 のものを集めて範囲を狭めていきます。

const int MAXQ = 100010;
int H[MAXQ];
ll L[MAXQ], R[MAXQ], ans[MAXQ];

int main() {
    int h, q;
    cin >> h >> q;
    ll low = 1, high = 1;
    for (int i = 0; i < h-1; i++) {
        low <<= 1;
        high <<= 1;
    }
    high = 2*high-1;
    vector<pair<ll, ll> > P;
    for (int i = 0; i < q; i++) {
        cin >> H[i] >> L[i] >> R[i] >> ans[i];
        ll tmp = (1ll<<(H[i]-1));
        ll mul = 1ll<<(h-H[i]);
        ll mini = (1ll<<(h-1)) + mul*(L[i]-tmp);
        ll maxi = (1ll<<(h-1)) + mul*(R[i]+1-tmp)-1;
        if (ans[i] == 1) {
            low = max(low, mini);
            high = min(high, maxi);
        } else {
            P.emplace_back(mini, maxi);
        }
    }
    vector<ll> cand;
    sort(P.begin(), P.end());
    for (auto p : P) {
        if (high <= p.first) {
            if (high == p.first) high--;
            break;
        }
        if (low < p.first) {
            ll cur = low;
            while (cur < p.first && cand.size() < 2) {
                cand.push_back(cur);
                cur++;
            }
        }
        low = max(low, p.second+1);
    }
    if (cand.size() == 2) {
        cout << "Data not sufficient!" << endl;
    } else if (cand.size() == 1) {
        if (low > high) cout << cand[0] << endl;
        else cout << "Data not sufficient!" << endl;
    } else {
        if (low > high) cout << "Game cheated!" << endl;
        else if (high==low) cout << low << endl;
        else cout << "Data not sufficient!" << endl;
    }
    return 0;
}