Python 3 can do bitsets too

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	163
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

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