Editing 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>