結果
問題 | No.1560 majority x majority |
ユーザー |
![]() |
提出日時 | 2021-06-25 22:16:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 1,190 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 81,000 KB |
最終ジャッジ日時 | 2024-06-25 08:31:20 |
合計ジャッジ時間 | 3,815 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 26 |
ソースコード
NN = 16KK = (1 << (1 << NN)) - 1I0 = KK // 3I1 = KK // 5I2 = KK // 17I3 = KK // 257def popcount(x):x -= (x >> 1) & I0x = (x & I1) + ((x >> 2) & I1)x = (x + (x >> 4)) & I2x = (x + (x >> 8)) & I3x += x >> 16x += x >> 32x += x >> 64x += x >> 128x += x >> 256x += x >> 512x += x >> 1024x += x >> 2048x += x >> 4096return x & 0xffffN, M = map(int, input().split())I = [[] for _ in range(M)]IV = {1 << i: i for i in range(M)}for i in range(N):for j, a in enumerate(input().split()):I[j].append(a)A = []for ii in I:A.append(int("0" + "".join(ii[::-1]), 2))mmm = (1 << N) - 1AND = [0] * (1 << M)PC = [0] * (1 << M)AND[0] = mmmPC[0] = NANS = [0] * (1 << M)ANS[0] = 1for i in range(1, 1 << M):a = i & -iif a == i:AND[i] = A[IV[a]]PC[i] = popcount(AND[i])else:AND[i] = AND[a] & AND[i^a]PC[i] = popcount(AND[i])pc = PC[i]ans = 0for j in range(N):if i >> j & 1:ij = i ^ (1 << j)ppc = PC[ij]if pc * 2 >= ppc:ans += ANS[ij]ANS[i] = ansprint(ANS[-1])