Разбор некоторых задач по БП

1.

Разбор некоторых задач по БП
Разбираем задачки…

2.

2 Бинпоиск 2.1 Задача из Квалификации - 2023

3.

2 Бинпоиск 2.1 Задача из Квалификации - 2023

4.

2 Бинпоиск 2.1 Задача из Квалификации - 2023

5.

2 Префиксные суммы. 2.1 Задача из Квалификации - 2023

6.

2 Бинпоиск 2.1 Задача из Квалификации - 2023
Это решение за O(1). А как решить с помощью бинарного поиска ?

7.

2 Бинпоиск 2.2 Задача C из Round 640 (Div 4)

8.

2 Бинпоиск 2.2 Задача C из Round 640 (Div 4)

9.

2 Бинпоиск 2.2 Задача C из Round 640 (Div 4)

10.

3 Бинпоиск 2.3 Задача F из Round 784 (Div 4)

11.

3 Бинпоиск 2.3 Задача F из Round 784 (Div 4)

12.

3 Бинпоиск 2.3 Задача F из Round 784 (Div 4)

13.

3 Бинпоиск 2.4 Задача Е из Round 935 (Div 3)

14.

3 Бинпоиск 2.4 Задача Е из Round 935 (Div 3)

15.

3 Бинпоиск 2.4 Задача Е из Round 935 (Div 3)

16.

3 Бинпоиск+динамика 2.5 Задача В из Round 914 (Div 2)

17.

3 Бинпоиск+динамика 2.5 Задача В из Round 914 (Div 2)

18.

3 Бинпоиск+динамика 2.5 Задача В из Round 914 (Div 2)
def solve(a):
n = len(a)
res = [0 for i in range(n)]
a1 = [(a[i], i) for i in range(n)]
DEBUG_INFO = 2
a2 = sorted(a1)
ps = [0 for i in range(n+1)]
for i in range(1, n+1):
from bisect import *
ps[i] = ps[i-1] + a2[i-1][0]
from itertools import
if DEBUG_INFO == 1:
print(a2)
from random import *
print(ps)
i = 0
while i < n:
while i + 1 < n and a2[i][0] == a2[i+1][0]:
i += 1
continue
si = ps[i + 1]
ix = bisect_left(a2, (si, 0))
si = ps[ix]
if DEBUG_INFO == 1:
print(str(i) + ')', si, ix)
while ix < n and ix > i and a2[ix][0] <= si:
si += a2[ix][0]
ix += 1
if DEBUG_INFO == 1:
print(str(i) + ')', si, ix)
res[a2[i][1]] = (ix - 1) if ix - 1 >= 0 else 0
if i > 0 and a2[i-1][0] == a2[i][0]:
j = i - 1
while j >= 0 and a2[j][0] == a2[i][0]:
res[a2[j][1]] = (ix - 1) if ix - 1 >= 0 else 0
j -= 1
i += 1
return res
*

19.

3 Бинпоиск+динамика 2.5 Задача В из Round 914 (Div 2)
def bf(a):
n = len(a)
res = [0 for i in range(n)]
a1 = [(a[i], i) for i in range(n)]
a2 = sorted(a1)
for i in range(n):
j, ni = 0, 0
sm = a2[i][0]
while j < n and a2[j][0] <= sm:
if j != i:
ni += 1
sm += a2[j][0]
j += 1
res[a2[i][1]] = ni
return res
def test():
for _ in range(1000):
n = randint(2, 8)
a = [randint(1, 11) for i in range(n)]
r1 = solve(a); r2 = bf(a)
if r1 != r2:
print(a, r1, r2)
if DEBUG_INFO == 2:
test()
print("===")
t = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]
print(*solve(a))