結果
問題 |
No.2895 Zero XOR Subset
|
ユーザー |
|
提出日時 | 2025-02-25 22:15:29 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,178 bytes |
コンパイル時間 | 410 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 93,972 KB |
最終ジャッジ日時 | 2025-02-25 22:15:52 |
合計ジャッジ時間 | 12,669 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | WA * 35 |
ソースコード
import os,sys,random,threading #sys.exit() 退出程序 #sys.setrecursionlimit(10**6) #调整栈空间 from random import randint,choice,shuffle #randint(a,b)从[a,b]范围随机选择一个数 #choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素 #shuffle(x)将一个可变的序列x中的元素打乱 from copy import deepcopy from io import BytesIO,IOBase from types import GeneratorType from functools import lru_cache,reduce #reduce(op,迭代对象) from bisect import bisect_left,bisect_right #bisect_left(x) 大于等于x的第一个下标 #bisect_right(x) 大于x的第一个下标 from collections import Counter,defaultdict,deque from itertools import accumulate,combinations,permutations #accumulate(a)用a序列生成一个累积迭代器,一般list化前面放个[0]做前缀和用 #combinations(a,k)a序列选k个 组合迭代器 #permutations(a,k)a序列选k个 排列迭代器 from heapq import heapify,heappop,heappush #heapify将列表转为堆 from typing import Generic,Iterable,Iterator,TypeVar,Union,List from string import ascii_lowercase,ascii_uppercase,digits #小写字母,大写字母,十进制数字 from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf #ceil向上取整,floor向下取整 ,sqrt开方 ,factorial阶乘 from decimal import Decimal,getcontext #Decimal(s) 实例化Decimal对象,一般使用字符串 #getcontext().prec=100 修改精度 from sys import stdin, stdout, setrecursionlimit input = lambda: sys.stdin.readline().rstrip("\r\n") MI = lambda :map(int,input().split()) li = lambda :list(MI()) ii = lambda :int(input()) mod = int(1e9 + 7) #998244353 inf = 1<<60 py = lambda :print("YES") pn = lambda :print("NO") DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上 DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)] # →↘↓↙←↖↑↗ # https://ac.nowcoder.com/acm/contest/vip-end-index?rankTypeFilter=-1&onlyCreateFilter=false&topCategoryFilter=13&categoryFilter=6&signUpFilter=&orderType=NO&page=2 a="952017399920288569 451858446262108084 886240341139629565 1083209362630747635 302300078868004734 70959011694240487 563183127104516007 573368636379906722 487812077660665598 428328753485692552 322226678025225988 334706974943227815 582515201643483740 90114147558262407 193417461628557699 532073624356201760 1056701691211756564 944519242233679147 406187315772119822 512732448833778204 471671796493869671 971160773025352752 800632481088808169 746440858548377367 63029653635118153 986525058019235035 1066156228900603876 1008343146355240018 67779500901204281 283240567447021599 804441770110159653 636407808138740246 150517164644385748 1017914634172230615 946978143762889912 692889267604855414 882784343565093200 1041329414428509828 435166130367045371 744056277479249749 270545219894026626 592529610628185175 1105211050812770463 826030319205928806 53219859280124349 50852841077810464 349967749832131952 545645726805896401 932225461750550730 567515881772479782 448716412612319997 261557245657558346 1125426257113218465 618781544471091317 429332580273521078 156852588170998277 804897808297939305 241888678245900606 805917337145776293 629334696027608755 929754715038747560 704542042362303636 802659276381135851 480383799008624377 263563808915253929 818526888384599387" a=[int(i) for i in a.split()] n=len(a) if 0 in a: print(1) print(a.index(0)+1) exit() base=[0]*61 #位数 pos=[None for _ in range(61)] def insert(x,idx): #插入一个数 tmp=Counter() tmp[idx]+=1 for i in range(60,-1,-1): if x>>i&1==0: continue if base[i]==0: base[i]=x pos[i]=tmp return 1 x^=base[i] tmp+=pos[i] return 0 if n>65: n=65 a=a[:n] for idx in range(n): if insert(a[idx],idx)==0: ans=[idx+1] res=Counter() for i in range(60,-1,-1): if a[i]>>i&1: res+=pos[i] a[i]^=base[i] for i,c in res.items(): if c%2==1: ans.append(i+1) print(len(ans)) ans.sort() print(*ans) exit() print(-1)