結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー |
|
提出日時 | 2021-03-05 23:05:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 448 ms / 2,000 ms |
コード長 | 1,801 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 81,408 KB |
最終ジャッジ日時 | 2024-10-07 04:33:41 |
合計ジャッジ時間 | 5,765 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N,M = mi()vec = []for i in range(M):A = int(input())B = li()y = int(input())c = 0for b in B:c += 1<<(b-1)vec.append((c,y))def solve(bit):bit_vec = []for i in range(M):c,y = vec[i]d = 2*c + (y>>bit & 1)bit_vec.append((c,d))base_c = []base_d = []for c,d in bit_vec:f_c,f_d = False,Falsefor b in base_c:c = min(c,c^b)if c:f_c = Truebase_c.append(c)for b in base_d:d = min(d,d^b)if d:f_d = Truebase_d.append(d)if f_d:if not f_c:return -1base_d.sort()assert 1 not in base_dpos = 0res = [0 for i in range(N)]for d in base_d:n = d.bit_length()assert pos < n-1tmp = d & 1for i in range(pos):tmp ^= (d>>(i+1)) & res[i]#print(pos,n,tmp,res)for i in range(pos,n-1):if tmp and d>>(i+1) & 1:res[i] = 1tmp = 0else:res[i] = 0pos = n-1assert pos == Nreturn resans = [0 for i in range(N)]for bit in range(30):tmp = solve(bit)if tmp == - 1:exit(print(-1))else:for i in range(N):ans[i] += tmp[i]<<bitprint(*ans,sep="\n")for c,y in vec:tmp = 0for i in range(N):if c>>i & 1:tmp ^= ans[i]#assert y==tmp