Bedao Mini Contest 06 - HARD
Xem dạng PDF
Gửi bài giải
Điểm:
0,90 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Tỉnh dậy sau một giấc ngủ sảng khoái, Muối cảm thấy tràn đầy năng lượng và bắt tay vào làm đống bài tập thầy cho. Nhưng đang hay thì đứt dây đàn, biết rằng Muối không phải học sinh tầm thường nên thầy giáo cho Muối một bài tập vô cùng khó, bài tập như sau:
Cho tập ~A~ ban đầu là rỗng và ~Q~ truy vấn, mỗi truy vấn có dạng:
~1~ ~v~: Nếu trong ~A~ chưa có ~v~ thì thêm ~v~ vào ~A~, ngược lại xóa ~v~ khỏi ~A~.
~2~ ~x~: Tìm tập ~B~ có kích thước nhỏ nhất sao cho với mỗi ~Y~ thuộc ~[1,x]~ đều tồn tại tập con của ~B~ có tổng bằng ~Y~, biết rằng các phần tử của tập ~B~ đều thuộc ~A~ và cùng một phần tử của tập ~A~ có thể xuất hiện nhiều lần trong tập ~B~.
Input
- Dòng đầu tiên gồm số nguyên ~Q~.
- ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn có dạng: ~1~ ~v~ hoặc ~2~ ~x~ ứng với truy vấn loại ~1~ hoặc loại ~2~
Output
- Ứng với mỗi truy vấn loại ~2~, in ra kích thước nhỏ nhất của tập ~B~ thỏa mãn yêu cầu. (Mỗi truy vấn in ra trên một dòng)
- Trong trường hợp không tìm được tập ~B~ thỏa mãn in ra ~-1~.
Sample Input
8
1 1
2 200
1 42
2 200
1 84
2 200
1 42
2 200
Sample Output
200
45
44
85
Subtask
- ~100\%~ số test có ~Q=200000~ và ~0 \le x,v \le {10}^{18}~
BÀI NÀY DÀNH CHO SMURF
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Unofficial Solution:
hay quá ông này pro rồi
ok :>