ジジ抜き [yukicoder No.814]

https://yukicoder.me/problems/no/814

前提知識

• 二分探索

解説

https://yukicoder.me/submissions/338394

問題文にもあるように、ジジは奇数枚・他は偶数枚になっている。
使えそうな性質がこれなので、これを使って解法を考えていく。
ある数以下のカードの枚数を見ると、ジジが含まれるなら奇数枚・含まれないなら偶数枚となる。
答えansで以下の関数で二分探索する。
check(x) := x以下のカードの枚数が奇数ならtrue
check関数内で普通に枚数を計算すると、10^18を超えるので、__int128を使うか、偶奇しか使わないのでmod2で総和を取っていけばいい。

int N; ll K[301010], L[301010], D[301010];
ll p[101];
//---------------------------------------------------------------------------------------------------
int check(ll x) {
	ll sm = 0;
	rep(i, 0, N) {
		if (x < L[i]) continue;
		ll n = (x - L[i]) / p[D[i]] + 1;
		ll x = max(0LL, n);
		x = min(x, K[i]);
		sm += x % 2;
	}
	return sm % 2 == 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	p[0] = 1;
	rep(i, 1, 101) p[i] = p[i - 1] * 2;

	cin >> N;
	rep(i, 0, N) cin >> K[i] >> L[i] >> D[i];

	ll ng = -1, ok = infl;
	while (ng + 1 != ok) {
		ll md = (ng + ok) / 2;
		if (check(md)) ok = md;
		else ng = md;
	}
	cout << ok << endl;
}