0

Формат входных данных

В первой строке записаны два целых числа n и m (1≤m,n≤10^5) – количество банок, которые были нашей мишенью в тот день, и количество совершённых в тот день выстрелов.

В i-ой из следующих n строк описывается положение i-ой банки. Положение задаётся координатами проекции банки на вертикальную плоскость. Проекция представляет из себя прямоугольник, стороны которого параллельны нанесённой на эту плоскость системы координат. Ось Y этой системы направлена вертикально вверх, а ось X – горизонтально. А прямоугольник задаётся парой точек – своей левой нижней и правой верхней вершинами.

Гарантируется, что ни одна пара этих прямоугольников не имеет ни одной общей точки.

В i-ой из следующих m строк описывается положение i-ой пули в стене. Пули заданы в том же порядке, в котором они выходили из наших дул. Сама стена строго вертикальна, поэтому мы можем считать, что положение задаётся координатами проекции пуль на вертикальную плоскость. Причём траектории движения пуль были строго перпендикулярна этой плоскости. Сами точки задаются парой координат в уже описанной выше системе координат.

Расстояние между банками и стеной по сравнению с расстоянием до стреляющих настолько мало, что мы им пренебрегаем.

Примечание

Значения координат по модулю не превышают 10^9.

Формат выходных данных

В первой и единственной строке выведите m чисел, i-ое из которых говорит, какую из банок i-я пуля прошла насквозь, если такая имеется. Если i не задела ни одну банку, то выведите −1, иначе выведите порядковый номер во входных данных банки, которую поразила i-я пуля.

Вот сам код:

x1 = []
y1 = []
x2 = []
y2 = []
bullet_x = []
bullet_y = []
shots = []

n, m = map(int, input().split())

for i in range(0, n):
    a, b, c, d = map(int, input().split())
    x1.append(a)
    y1.append(b)
    x2.append(c)
    y2.append(d)

for i in range(0, m):
    x, y = map(int, input().split())
    bullet_x.append(x)
    bullet_y.append(y)

for j in range(0, m):
    b = False
    for i in range(0, n):

        if (x2[i] >= bullet_x[j] >= x1[i]) and (y2[i] >= bullet_y[j] >= y1[i]):
            b = i + 1

    if b and b not in shots:
        shots.append(b)

    else:
        shots.append(-1)

for i in range(len(shots)):
    print(shots[i], end=" ")
4
  • эта программа заваливает 57 тест на е2?
    – zuppi
    1 ноя 2019 в 18:03
  • @zuppi так точно, вы как то решили эту проблему?
    – S1riyS
    1 ноя 2019 в 18:12
  • Увы, но нет) Код был переписан на с++, однако алгоритм провалился на 57 тесте по времени.
    – zuppi
    1 ноя 2019 в 20:15
  • А вы решили задачи под буквой D ?
    – S1riyS
    2 ноя 2019 в 4:48

3 ответа 3

0

просто перепишите код на плюсах и он пройдет 57 тест ---- D1-D4

n,t,c =map(int, input().split())
req = input().split()
deps = {}
for i in range (n):
    name = input()
    deps[name] = list(input().split())[1:]
used = set()
order = []
def top_sort(cur):
    used.add(cur)
    for dep in deps[cur]:
        if dep not in used:
           top_sort(dep)
    order.append(cur)
for name in req:
    if name not in used:
       top_sort(name)
print(len(used))
if c == 2:
    print(*order)
15
  • я не знаю с++ почти что полностью, можешь отправить решение?
    – S1riyS
    2 ноя 2019 в 11:08
  • пока что в процессе переписывания
    – Exdet
    2 ноя 2019 в 11:10
  • прошу, отправь сюда, когда перепишешь
    – S1riyS
    2 ноя 2019 в 11:14
  • D1-D4 (ты вроде просил)
    – Exdet
    2 ноя 2019 в 11:15
  • ну если есть, то можешь отправить
    – S1riyS
    2 ноя 2019 в 11:16
0
m, n = map(int, input().split())
bank = []
bull = []
for i in range(m):
    bank.append(list(map(int, input().split())))
for i in range(n):
    bull.append(list(map(int, input().split())))
shoted = [True] * m
ns = [-1] * n
for i in range(n):
    for j in range(m):
        if bank[j][0] <= bull[i][0] <= bank[j][2] and bank[j][1] <= bull[i][1] <= bank[j][3] and shoted[j]:
            shoted[j] = False
            ns[i] = j + 1
            break
for k in ns:
    print(k, end=' ')

Немного более короткий код на Python, но тоже проваливает тест #57, из-за слишком долгого выполнения

3
  • Только D1. Остальные не осилил 2 ноя 2019 в 7:44
  • отправьте пожалуйста решение D1, а то мне в голову вообще никаких решений не приходит
    – S1riyS
    2 ноя 2019 в 7:47
  • Последний цикл можно сразу принтить во вложенном
    – eri
    4 ноя 2019 в 2:31
0
n, m = map(int, input().split())
b = []
for i in range(n):
    b.append(list(map(int, input().split())))
u = b[:]
for i in range(m):
    x, y = map(int, input().split())
    for j in b:
        if j[0] <= x <= j[2] and j[1] <= y <= j[3]:
            print(u.index(j) + 1, end=' ')
            b.remove(j)
            break
    else:
        print(-1, end=' ')

Еще более короткий код, но также валится на 57

0

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.