4088 - BSTQ

Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:

1 x – adaugă numărul x în A 2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare?

Cerința

Să se răspundă la cele n întrebări.

Date de intrare

Fișierul de intrare bstqin.txt conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2.

Date de ieșire

Fișierul de ieșire bstqout.txt va conține atâtea linii câte operații de tip 2 sunt în fișierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• Numerele care se adaugă în A sunt numere întregi reprezentate pe 32 de biți cu semn.
• Este garantat că la orice operație 2 k valoarea lui k este mai mică sau egală decât numărul de elemente din A.
• Este garantat că numerele care se introduc în A prin operația de tip 1 sunt generate aleator.

Exemplul 1:

bstqin.txt

16
1 7
1 9
1 3
1 7
2 3
2 2
1 10
1 2
2 4
2 5
1 5
2 3
1 8
1 10
1 4
1 3

bstqout.txt

Datele de intrare corespund restrictiilor impuse
7
7
7
9
5

Exemplul 2:

bstqin.txt

bstq

bstqout.txt

Datele de intrare nu corespund restrictiilor impuse

Explicație

La prima întrebare, 2 3, deja în A sunt valorile 3,7,7,9, deci a treia valoare este 7. La a doua întrebare, 2 2, A = 3,7,7,9, deci a doua valoare este 7. La a treia întrebare, 2 4, A = 2,3,7,7,9,10, deci a patra valoare este 7. La a patra întrebare, 2 5, A = 2,3,7,7,9,10, deci a cincea valoare este 9. La a cincea întrebare, 2 3, A = 2,3,5,7,7,9,10, deci a treia valoare este 5.

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

from bisect import insort_left

def validare(nr_n, operatii):

   if nr_n > 200000:
       raise ValueError
   for operation in operatii:
       if operation[0] == 1 and (operation[1] < -2147483648 or operation[1] > 2147483647):
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def process_operations(operatii, fisier_out):

   a = []
   for operation in operatii:
       if operation[0] == 1:
           insort_left(a, operation[1])
       elif operation[0] == 2:
           fisier_out.write(str(a[operation[1] - 1]) + '\n')

if __name__ == '__main__':

   file_in = open("bstqin.txt", "r")
   file_out = open("bstqout.txt", "w")
   try:
       n = int(file_in.readline())
       operations = [list(map(int, file_in.readline().split())) for _ in range(n)]
       validare(n, operations)
       process_operations(operations, file_out)
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>