Python 3 can do bitsets too

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Python 3 has unlimited size integers, which can function as dynamic size bitsets when doing bitwise operations. Python is still about 3x slower than C++ bitsets with no pragmas and 10x slower than C++ with avx2+O3 pragmas. However, the Python integers have dynamic size, so there some potential of making a problem that requires dynamic bitsets purely to mess with people who use C++ standard library bitsets.

Anyways, here's some simple code I wrote in Python for https://ecna22.kattis.com/problems/amusicalquestion. It is AC in 0.16s.

Code

c, n = map(int, input().split())
songs = [int(i) for i in input().split()]

mask = (1 << (c + 1)) - 1


valid = [0 for _ in range(c + 1)]
valid[0] = 1

for s in songs:
    if s <= c:
        for i in range(c, s - 1, -1):
            valid[i] = (valid[i] | (valid[i] << s) | valid[i - s]) & mask
        for i in range(s - 1, -1, -1):
            valid[i] = (valid[i] | (valid[i] << s)) & mask

best = -1
bc2 = -1
bc1 = -1

for c2 in range(c + 1):
    c1 = valid[c2].bit_length() - 1
    if c1 != -1 and best <= c1 + c2 and c2 <= c1:
        best = c1 + c2
        bc1 = c1
        bc2 = c2
print(bc1, bc2)

	Rev.	Lang.	By	When	Δ	Comment
	en1		jzhe727	2023-10-28 08:28:42	1333	Initial revision (published)

Rev.

Lang.

When

Comment

en1

jzhe727

2023-10-28 08:28:42

1333

Initial revision (published)

History