結果
問題 | No.1820 NandShift |
ユーザー |
|
提出日時 | 2021-08-29 10:19:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 924 bytes |
コンパイル時間 | 628 ms |
コンパイル使用メモリ | 82,020 KB |
実行使用メモリ | 64,128 KB |
最終ジャッジ日時 | 2024-11-25 21:40:51 |
合計ジャッジ時間 | 2,957 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
from collections import defaultdict N, M = map(int, input().split()) X = int(input(), 2) As = [int(input(), 2) for _ in range(N)] TMP1 = 10 ** 7 TMP2 = 10 ** 7 + 1 d = defaultdict(int) for i, A in enumerate(As, start=1): d[i] = A B = 1 << M queries = [] def shift(x, i): queries.append((1, x, i)) d[x] = (d[i] << 1) % B def nand(x, i, j): queries.append((2, x, i, j)) d[x] = (~(d[i] & d[j])) % B def or_(x, i, j): nand(TMP1, i, i) nand(TMP2, j, j) nand(x, TMP1, TMP2) ZERO = 10 ** 8 N_ONE = ZERO - 1 nand(N_ONE, ZERO, ZERO) N_TWO = N_ONE - 1 shift(N_TWO, N_ONE) ONE = N_TWO - 1 nand(ONE, N_TWO, N_TWO) # print(d[ZERO]) # print(d[N_ONE]) # print(d[N_TWO]) # print(d[ONE]) for b in reversed(range(M)): shift(0, 0) if (X >> b) & 1: or_(0, 0, ONE) # print(d) assert d[0] == X, '\n' + bin(d[0]) + '\n' + bin(X) print(len(queries)) for q in queries: print(*q)