結果

問題 No.3718 XOR Escape
コンテスト
ユーザー Kude
提出日時 2026-09-18 23:05:37
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 26 ms / 2,000 ms
+ 136µs
コード長 2,229 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 79 ms
コンパイル使用メモリ 80,640 KB
実行使用メモリ 54,784 KB
最終ジャッジ日時 2026-09-18 23:05:47
合計ジャッジ時間 2,088 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def solve(a, b, c, n):
    a, b, c = sorted((a, b, c))
    assert 1 <= a < b < c
    if c == 3: return n >> 2
    ans = 0
    n0 = n
    # while n > 0:
    #     if n0 - n >= 30:
    #         print(a,b,c,n0)
    #         exit(0)
    #     nn = n - 1
    #     while nn >= 0:
    #         if n ^ nn != a and n ^ nn != b and n ^ nn != c:
    #             ans += 1
    #             break
    #         nn -= 1
    #     if nn <= 0:
    #         return ans
    #     if n - nn == 1:
    #         n = nn
    #         break
    #     n = nn
    ans += n
    for x in a, b, c:
        if x & (x + 1) != 0: continue
        x = (x + 1) >> 1
        # x + 2x t <= n
        if n >= x:
            ans -= (n - x) // (2 * x) + 1
    return ans
    # else:
    #     ans -= (n - 1) // 2 + 1
    #     c += 1
    #     ans -= 

        
    for k in range(60):
        # 2^k + 2^(k+1)x <= n
        if 1 << k > n:
            break
        cnt = ((n - (1 << k)) >> (k + 1)) + 1
        v = 1 << k
        skip = 0
        nv = v - 1
        while nv >= 0:
            if v ^ nv != a and v ^ nv != b and v ^ nv != c:
                break
            skip += 1
            nv -= 1
        print(k,cnt,skip)
        ans -= cnt * skip
    return ans
n, a, b, c = map(int, input().split())
print(solve(a, b, c, n))
# print(solve(1,6,7,6))
exit(0)

for a in range(1, 130):
    for b in range(a, 130):
        for c in range(b, 130):
            if a ^ b ^ c != 0: continue
            assert a < b < c
            dp = [0] * 200
            for i in range(1, 200):
                dp[i] = max((dp[j] + 1 for j in range(i) if j^i != a and j^i != b and j^i != c), default=0)
            for i in range(1, 200):
                i0 = i
                cnt = 0
                while i > 0:
                    ni = i-1
                    while ni >= 0:
                        if i^ni != a and i^ni != b and i^ni != c:
                            cnt += 1
                            break
                        ni -= 1
                    i = ni
                if c == 3: assert dp[i0] == i0 >> 2
                if dp[i0] != solve(a,b,c,i0):
                    print(a, b, c, i0, dp[i0], cnt, solve(a,b,c,i0))
                    exit(0)
0