Помощь с олимпиадной задачей.

какая же бессмысленная дрочильня

на кой она тебе?

что бы пройти собеседование в яндекс!!!!!!!1юххуууу!!!!!!!

«некоторое число m»,

В задаче нет ничего про «некоторое число m», ютуб никто смотреть не будет.
Скорее всего там про сокращение дробей, гугли в яндексе.

для двоичного поиска

Нафиге тебе двоичный поиск? Никто не просит двоичный поиск. Задача по-сути в том, чтобы сократить дроби и отсортировать. После этого проходишь и собираешь указанные по номеру дроби (это просто для удобства проверки решения).

В решении большинства задач вводятся переменные. В ютуб разборе andrewzta использует эту переменную. Также в оффициальном разборе текстовом тоже вводят эту переменную. Твой бред про сокращение дробей даже комментировать лень.

Там есть ограничение по памяти и по времени. Поэтому нельзя аллоцировать весь массив дробей. В этом и сложность.

ограничение по памяти и по времени

В каком месте? По ссылке нет никакого ограничения. Более того русским по белому написано «сократим каждую дробь и отсортируем их по неубыванию». Да и задача называется «Сортировка дробей».

хорошо, значит там не полный текст задачи. my bad. не увидел.

Я нашёл там мелким шрифтом «Время: 3 сек. Память: 32 Мб». Ну хз, смотря какой fabric комп, смотря какой язык.

а что это я. Там есть ограничения по ссылке. Память 32мб, время 3сек. Сверху же написано.

жду олимпиадников, если они тут обитают…

Хм, тогда я бы попробовал так. Берём любую дробь, перебираем все комбинации и считаем, сколько дробей меньше взятой. Если нужная по номеру дробь в числе этих, то берём дробь меньше и повторяем двоичным поиском. В другую сторону также. Например нужно 7 дробь, меньше тестовой насчитали 10. Значит наша дробь среди этих 10. Делим нашу дробь пополам, снова считаем, нашлось 5. Т.о. искомая дробь между половиной и исходной и т.д. пока не останется одна дробь.

что бы пройти собеседование в яндекс!!!!!!!1юххуууу!!!!!!!

а оно тебе надо?

tle :)

#import sys
from  fractions import Fraction as f  # noqa: F401
from collections import defaultdict
from heapq import heapify,heappush,heappop
#sys.stdin=open('input.txt')
n,q=(int(v)for v in input().split())
a=sorted(int(v)for v in input().split())
b=[int(v)for v in input().split()]
c=[int(v)for v in input().split()]
d=defaultdict(list)
for i,v in enumerate(c):d[v].append(i)
cm=max(d)#max(c)
o=[0]*q
heapify(p:=[(f(a[0],b[j]),0,j)for j in range(n)])
for e in range(1,max(d)+1):
    v,i,j=heappop(p)
    if e  in d:
        for k in d[e]:
            o[k]=v
    if (i:=i+1)<n:
            heappush(p,(f(a[i],b[j]),i,j))
for v in o:
    print(v.numerator,v.denominator)

лол fractions оказывается очень очень медленное

ибо

21655357	20.06.2024 13:53:54	Python	Time limit exceeded	68	3,203	24 Мб
21655348	20.06.2024 13:46:10	Python	Time limit exceeded	34	3,156	2274 Кб

чиста замена вместо (f(a,b[j]),i,j) на (a/b[j],i,j)

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

Поэтому смотри, алгоритм там тупейший, тебе нужно 2 функции:

boolean compare(int[] v1, int[] v2) 

void simplify(int[] v) 

Дальше всё просто, пишешь любой алгоритм сортировки который нравится, используя внутри функцию compare для сравнения дробей, которая может просто привести их к общему знаменателю перемножением (ибо 10^5 * 10^5 это всего то 10^10). Потом выводишь в нужном порядке прогоняя через simplify. Унутре у неё поиск наибольшего общего делителя для числителя и знаменателя и деление на него.

При наложенных условиях тебе даже не нужно парится хитрыми алгоритмами поиска нок и нод, даже брутфорсом должен уложиться, если там не 8086 проц.

вещественное приближение

Кажется ты херню нашёл а не разбор. Там целых для решения достаточно.

ох, умник, почитай выше, нельзя аллоцировать массив для сортировки. ограничение по памяти. думаешь я до решения твоего уровня не допёр бы. или ты думаешь, что итмошный олимпик препод будет давать неправильный разбор.

лолол:

mle на 34 если в лоб:

import sys
from  fractions import Fraction as f  # noqa: F401
sys.stdin=open('input.txt')
n,q=(int(v)for v in input().split())
a=sorted(int(v)for v in input().split())
b=sorted(int(v)for v in input().split())
c=[int(v)-1 for v in input().split()]
z=sorted((v/w,i,j)for i,v in enumerate(a)for j,w in enumerate(b))
for p in c:
    _,i,j=z[p]
    t=f(a[i],b[j])
    print(t.numerator,t.denominator)

тут проблема не всравнении - ну да можно сравнивать своим компаратором приведённые дроби через знак произведение средних на произведение крайних

а дробь самому приводить через math.gcd ( в случае питона нам же лень самим)

тут спецом закавыка в тестах не допускающих полное линейное сканирование итогового списка - поэтому у топик стартера вопрос как бинпоиском искать cj элемент в n упорядоченных списках

вон посмотри сырцы - они валятся либо на 68 тесте по tle ( так на 34 но если отказаться от fractions и использовать просто float деление то на 68)

либо на 34 mle чисто список не помещается

возможно на с можно запихать лобовое - хотя врядли

нельзя аллоцировать массив

А входные данные ты куда денешь?

Ну переделай аргументы в compare(int m1, int d1, int m2, int d2) и т.п. Просто писать не так удобно.

см условия задачи

размер выходного списка дробей 10**10 ограничения системы 32мб -

реальная подсказка это строка:

Дополнительно выполняется неравенство n · q ≤ 10**5

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

А что ему сказать? «Не берите xionovermazes»?

Ага, так и напишу.

ты публично обгадился не внимательно прочитав условия/ограничения и чето продолжаешь писать. на яндекс твой мне по-барабану, это ирония была. решаю задачи что бы мозг напрягать.

ты публично обгадился

Ты немного заблуждаешься.

Поэтому смотри, алгоритм там тупейший

И пишешь тривиальное решение, которое не проходит MLE. Причем сверху упомянуто в чем сложность задачи.

Ты даже задачу не потрудился принести в ОП и спросил про какой-то непонятный m из видосика. Протетить что-то с телефона я тем более не могу.

Так в Яндекс или в Yahoo?🤔

Ничего не понятно, но очень интересно. ;) Если я правильно понял задачу, то:

      ⍝ входные данные
      a←3 4 1 2
      b←2 3 4 5
      c←1 16 2 4 5 6 10 

      ⍝ делим a на b
      x←16⍴ a∘.÷b
      x
1.5 1 0.75 0.6 2 1.333333333 1 0.8 0.5 0.3333333333 0.25 0.2 1 0.6666666667 0.5 0.4

      ⍝ сортируем
      y←x[⍋x]
      y
0.2 0.25 0.3333333333 0.4 0.5 0.5 0.6 0.6666666667 0.75 0.8 1 1 1 1.333333333 1.5 2

      ⍝ выбираем
      y[c]
0.2 2 0.25 0.4 0.5 0.5 0.8 1.5

→ https://tryapl.org/

Сложность задачи в том, что нельзя аллоцировать массив всех дробей n^2 и затем соритровать его. Ограничение по памяти.

не понимаю как определяется «некоторое число m»

Это произвольное число. В условиях задачи целесообразно взять 5000 в качестве начального значения. Число m - предположение о значении дроби, мы находим точное значение m путём бинарного поиска среди всех дробей, в процессе которого делаем бинарный поиск среди каждой группы дробей одного делителя.

Получается, что задача больше на нахождение наибольшего общего делителя двух чисел. Потому что остальное все тривиально.

Не совсем, там массив не влазит в ограничение пл памяти. Принципиально это на самом деле ничего не меняет, просто поиск значений нужно вести не после полной сортировки а в процессе. Тем более, что до конца может быть и не нужно доходить.

тривиальное решение

Нетривиальное судя по всему не сильно будкт отличаться. Вечером из дома может и тесты прогнать смогу.

Задачу не читал, памяти хватает на 8 копий массивов float[10^6].

double[10^10] нужно для условий задачи.

А как вы дробь обратно переведете из double в int / int?

вопрос как бинпоиском искать cj элемент в n упорядоченных списках

Тут нет никаких упорядоченных списков. Если ты упорядочишь A и B это не значит что после сокращения дроби будут в нужном порядке.

Такое в мыслях витало, но вы хорошо выразили. Правда почему именно 5000 я не понял. Я это сейчас вижу так:

0. Соритируем a,b.
1. Берем любую дробь m, допустим по середине a[n/2] / b[n/2].
2. Введем число d, которое будет означать сколько дробей менее m.
3. Проходимся бинарным поиском внутри каждой группы с одинаковым знаменателем. И для каждой группы находим сколько значений менее m. Назовем это число для каждой группы n_i.
4. Очевидно, что если d > c(запрос), то нужно число большее m, в противном случае, нужно число большее m.
5. Для каждой группы имеем по одному кандидату. По сути это либо n_i либо n_i-1. В зависимости от условия 4.
6. Имея n кандидатов, выбираем тот который ближе всего находится к m. m = new_candidate.
7. Повторяем шаги 2-6 пока d != c.

Я отпишу реализацию чуть позже. В реализации нужно ещё аккуратно с индексами кандидатов, чтобы за границы не уйти.

n_i - 1

По идее рядом с числом m просто хранить те индексы(числитель и знаменатель) из которых оно было сделано.

Ответ-то нужен в сокращенном виде. Т.е. дробь должна быть сокращена

ну это уже не вызывает трудностей. сократить дробь зная числитель и знаменатель алгоритмом Эвклида.

Дробь не меняет значения после сокращения. У тебя n упорядоченных групп из n чисел каждая.

А чем/как вы профилируете так ловко?

Зачем сокращать дроби? Перемножаешь числитель со знаменателем другой дроби и сравниваешь.

PS задачу не читал, по ссылкам не хожу

Дробь не меняет значения после сокращения

Ты не можешь хранить все дроби. Это запрещено условием.

Да, но данные из условия тебе придется всосать, поэтому грубо говоря все числа у тебя есть, а упорощать можно перед печатью, т.к. тебя не спрашивали про все числа.