[백준] 11723번: 집합

https://www.acmicpc.net/problem/11723

initial

its very hard to implement this via bitmask

Initial confusion is this 1<<num-1 way. So if we wanna add lets say value 6, 1<<num-1 is shifting 1 by 5 bits so is 10000 which isnt value 6.

Actually, we are not adding value 6 but we are just marking the 6th bit as 1. Imagine we have a list of bits from 1st to 20th bit. A single integer s is to represent a 20-bit bitmask

V IMPT
1 << (x-1) either shifts 1 by x-1 position or shifts 1 to xth bit. What i mean is if 1 << (2-1), 1<<1 so 10.

So 1 << 20 is 1<< (21-1), which essentially is putting 1 in 21st bit. Then we minus 1 to make 1st to 20th bit 1 for "all" operations.

solution

import sys
input = sys.stdin.readline

n=int(input())
s=0
for _ in range(n):
    h = input()
    test = h.split()
    if len(test)>1:
        hola,numb = test
    else:
        hola,numb = test[0],0
    numb = int(numb)
    if hola=="add":
        s |= 1 << (numb-1)
    elif hola=="remove":
        s &= ~(1 << (numb-1))
    elif hola =="toggle":
        s ^= 1<<(numb-1)
    elif hola =="check":
        if s & (1<< (numb-1)):
            print(1)
        else:
            print(0)
    elif hola=="all":
        s = (1<<20) -1
    else:
        s=0

complexity

time: o(n) but these bitwise operations are constant time
space: o(1) cuz bits