Python 3 can do bitsets too

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
4	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

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