보통 이런 문제들은 C나 C++ 계열에 초점이 맞춰져 있습니다. 잘 보시면 메모리 제한이 8MB로 되어 있는데 이건 메모리 보너스 없이는 원소를 일일이 입력받아서 전부 저장조차 해놓을 수 없을 정도로 작은 크기죠. 하지만 백준에서는 파이썬의 특징 때문에 모든 문제에 시간 제한 +10초, 메모리 제한 +512MB라는 보너스를 부여하고 있기 때문에 이런 문제에선 저 제한이 먹혀들지 않을 뿐입니다.

원래 문제의 의도는 1비트 단위로 플래그를 체크해서 입력 범위를 전부 커버할 수 있도록 만드는 것인데 파이썬으로 풀면 그다지 의미가 없는 듯 합니다.

파이썬은 거의 공부하지 않아서 잘 모르겠지만 아마 기본 자료구조 중에서 중복을 허용하지 않는 정렬된 자료구조가 있을 거라고 생각합니다. 그거라면 O(1)은 아니라도 O(log N) 정도에 찾을 수 있겠고 시간이 모자라진 않을 거 같네요.

아니면 원래 문제 의도와 비슷하게, 다만 비트 단위가 아닌 그냥 리스트 원소가 하나의 수에 대응되게끔 플래그 리스트를 짜도 되겠네요.