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; }