Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II
解法
まず 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; }