結果

問題 No.3550 Another Rurumaru Function Problem
コンテスト
ユーザー tassei903
提出日時 2026-05-27 12:28:39
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 156 ms / 2,000 ms
コード長 1,816 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 208 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 113,408 KB
最終ジャッジ日時 2026-05-27 12:28:48
合計ジャッジ時間 7,442 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
# input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

def f(x):
    for j in range(0, m, 2):
        x ^= 1 << j
    return x

def naive(n, a):
    for i in range(n):
        a[i] = f(a[i])
    ans = 0
    for i in range(1, 1 << n):
        x = 0
        for j in range(n):
            if i >> j & 1:
                x |= a[j]
        ans = max(ans, f(x))
    return ans

def solve(n, a):
    for i in range(n):
        a[i] = f(a[i])
    ok = [1] * n
    ans = 0
    for j in range(m-1, -1, -1):
        if j % 2 == 1:
            if any(ok[i] and a[i] >> j & 1 for i in range(n)):
                # print(j)
                ans |= 1 << j
        else:
            x = 0
            cnt = 0
            for i in range(n):
                if ok[i] and a[i] >> j & 1 == 0:
                    x |= a[i]
                    cnt += 1
            # print("!", j, x, ans)
            if x >> j + 1 == ans >> j + 1 and cnt > 0:
                # print("!", j)
                for i in range(n):
                    if a[i] >> j & 1 == 1:
                        ok[i] = 0
            else:
                ans |= 1 << j
        # print(j, ans)
        

    return f(ans)



m = 30

# print(solve(1, [7]))

# from random import randint
# for _ in range(1000):
#     n = randint(1,8)
#     a = [randint(0, 7) for i in range(n)]
#     t1 = solve(n, list(a))
#     t2 = naive(n, list(a))
#     if t1 != t2:
#         print(n)
#         print(a)
#         print(t1, t2)
#         break

n = ni()
a = na()

print(solve(n, a))
0