Bedao Mini Contest 06 - HARD

View as PDF

Submit solution


Points: 0.90 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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


Comments

Please read the guidelines before commenting.



  • -9
    minh47857   commented on Sept. 4, 2021, 11:21 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 5
      SPyofgame   commented on Sept. 10, 2021, 4:36 p.m.

      Unofficial Solution:

      https://hackmd.io/@SPyofgame/bedao_m06_hard


      • 4
        someone   commented on Sept. 10, 2021, 8:53 p.m.

        hay quá ông này pro rồi


    • 14
      SPyofgame   commented on Sept. 4, 2021, 1:59 p.m.

      ok :>