20919번 - XOR 자료구조 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 192 | 59 | 37 | 27.612% |
문제
Albert는 최근 (2진수) XOR 연산과 자료구조에 흠뻑 빠져있다.
Albert는 XOR에 관련된 여러 가지 연산을 효율적으로 할 수 있는 자료 구조를 만들고 싶다.
처음에는 n개의 정수를 포함한 집합 S0을 이용하여 자료 구조를 초기화 하며, 그 이후 q개의 연산을 수행하여 옳은 답을 출력해야한다.
각 연산은 아래 다섯 가지 중 하나이며, 일부 연산은 자료 구조에 저장된 정수 집합에 새로운 정수를 추가하거나 정수를 지우기도 한다 (따라서 그 이후의 연산은 영향을 받게 된다).
- find_min(v): 현재 자료 구조에 저장된 정수 집합이 S라면, (v XOR s) 값이 최소가 되는 S의 원소 s를 찾아 (v XOR s) 값을 출력한다. S는 변경되지 않는다.
- find_max(v): 현재 자료 구조에 저장된 정수 집합이 S라면, (v XOR s) 값이 최대가 되는 S의 원소 s를 찾아 (v XOR s) 값을 출력한다. S는 변경되지 않는다.
- add(v): 현재 자료 구조에 저장된 정수 집합 S에 v를 추가한다. 추가한 후, S에 저장된 고유한 정수의 개수를 출력한다.
- remove_min(): 현재 자료 구조에 저장된 정수 집합 S의 원소 중 가장 작은 수를 출력한 후, 이를 삭제한다. 만약 가장 작은 수가 여럿이라면 모두 삭제한다.
- remove_max(): 현재 자료 구조에 저장된 정수 집합 S의 원소 중 가장 큰 수를 출력한 후, 이를 삭제한다. 만약 가장 큰 수가 여럿이라면 모두 삭제한다.
예를 들어, S0 = {1,1, 3, 3} 이고 아래와 같은 순서로 총 q = 7개의 연산을 적용한다고 해보자.
- find_min(2): (1 XOR 2) = 3 이고 (2 XOR 3) = 1 이므로 1을 출력해야한다. 연산 적용 후, S는 바뀌지 않으므로 S = {1, 1, 3, 3} 이다.
- find_max(2): (1 XOR 2) = 3 이고 (2 XOR 3) = 1 이므로 3을 출력해야한다. 연산 적용 후, S는 바뀌지 않으므로 S = {1, 1, 3, 3} 이다.
- add(2): S에 새로운 원소를 추가하여 S = {1, 1, 2, 3, 3}이 된다. 중복을 제외하면 총 3개의 고유한 정수가 있으므로 3을 출력한다.
- remove_min(): S의 원소 중 가장 작은 수는 1이므로 1을 출력하고, 모두 삭제한다. 연산 적용 후, S = {2, 3, 3} 이다.
- remove_max(): S의 원소 중 가장 큰 수는 3이므로 3을 출력하고, 모두 삭제한다. 연산 적용 후, S = {2} 이다.
- find_min(2): (2 XOR 2) = 0 이므로 0을 출력해야한다.
- find_max(2): (2 XOR 2) = 0 이므로 0을 출력해야한다.
위의 예제의 경우, 올바른 결과는 (연산 적용 순서대로) [1, 3, 3, 1, 3, 0, 0]이 된다.
입력으로 n, S0, q, 그리고 q개의 연산을 받아 총 q개의 정수 (각 연산을 적용한 후 얻은 결과)를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 n과 q가 공백으로 구분 되어 주어진다.
둘째 줄에는 집합 S0에 포함된 n개의 정수가 공백으로 주어진다.
다음 q줄에 걸쳐 각 줄에 하나의 연산이 주어진다.
각 줄에는 1개 혹은 2개의 정수가 (공백으로 구분되어) 주어지는데, 첫 수는 연산의 종류를 나타내며 {1, 2, 3, 4, 5} 중 하나이다.
문제 본문에 설명된바와 같이, 1은 find_min, 2는 find_max, 3은 add, 4는 remove_min, 그리고 5는 remove_max 연산을 나타낸다.
연산 1-3의 경우에만 같은 줄에 두 번째 정수 "v"가 주어진다.
출력
각 연산을 적용한 후 자료 구조가 출력해야하는 올바른 값을 한 줄에 하나씩 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n, q ≤ 50,000
- 연산과 함께 주어지는 모든 값 v에 대해 0 ≤ v < 2^25
- S0에 주어진 모든 원소 s에 대해 0 ≤ s < 2^25
- 모든 연산에 대하여, 각 연산을 처리하기 전이나 후에 S의 원소가 없는 경우는 입력으로 주어지지 않는다.
예제 입력 1
3 4 7 1 1 3 3 1 2 2 2 3 2 4 5 1 2 2 2 10 11 1 3 5 7 9 2 4 6 8 10 1 6 1 8 2 6 2 8 3 10 4 5 1 2 1 17 2 2 2 17 5 11 2 5 8 13 17 1 6 1 8 2 6 2 8 3 10 4 5 1 2 1 17 2 2 2 17
예제 출력 1
1 3 3 1 3 0 0 0 0 15 15 10 1 10 0 18 11 25 3 0 23 25 6 2 17 7 20 15 28
케이스 1: 본문에서 사용한 예제이다.
케이스 2: 추가 설명 없음.
케이스 3:
연산 시작 전: S = {2, 5, 8, 13, 17}
- find_min(6): (6 XOR 5) = 3
- find_min(8): (8 XOR 8) = 0
- find_max(6): (6 XOR 17) = 23
- find_max(8): (8 XOR 17) = 25
- add(10): S = {2, 5, 8, 10, 13, 17} (6개의 고유한 정수)
- remove_min(): S = {5, 8, 10, 13, 17} (2를 삭제함)
- remove_max(): S = {5, 8, 10, 13} (17을 삭제함)
- find_min(2): (2 XOR 5) = 7
- find_min(17): (17 XOR 5) = 20
- find_max(2): (2 XOR 13) = 15
- find_max(17): (17 XOR 13) = 28
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호