Блокировка чтения и записи с приоритетом записи
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Темы
- Асинхронность и потоки
- Стек, очередь, связные списки
Корутина i приходит в момент arrivals[i] за блокировкой: читатель (kinds[i] = "r") или писатель ("w"). Получив блокировку, она держит её ровно holds[i] мс и отпускает. Читатели могут держать блокировку вместе, писатель — только один, без читателей.
Ожидающие стоят в одной общей очереди в порядке прихода (пришедшие в один момент — по возрастанию индекса). Пришедшая корутина сразу получает блокировку, только если очередь пуста и блокировка совместима с её текущими владельцами; иначе она встаёт в конец очереди. Поэтому читатель, пришедший, когда ждёт писатель, встаёт за ним (приоритет записи). Из очереди блокировку получают с головы: писатель — когда владельцев нет; читатель — когда нет писателя-владельца, и тогда за ним сразу проходят все читатели, стоящие подряд до ближайшего писателя в очереди. Корутина, которая не получила блокировку за timeout мс после прихода, сдаётся и уходит из очереди; если ушёл писатель, стоявшие за ним читатели могут сразу войти к текущим читателям.
В один момент события идут так: сначала отпускают блокировку все, чьё время истекло; затем сдаются те, у кого в этот момент кончилось ожидание (если в этот момент они ещё не получили блокировку); затем приходят новые корутины по возрастанию индекса. После каждого шага очередь сразу проходит, насколько может.
Верните для каждой корутины момент, когда она отпустила блокировку, или -1, если она сдалась. Функция асинхронная: удобно обрабатывать события по времени и ждать каждого таймером; текущее время в миллисекундах: Date.now() в JS/TS и round(asyncio.get_running_loop().time() * 1000) в Python. В тестах ожидания идут по виртуальным часам и не занимают реального времени. Ограничения: до 40 корутин, моменты прихода от 0 до 100000 в любом порядке, holds[i] и timeout от 1 до 1000000. Для пустых списков ответ [].
Пример: arrivals = [0, 1, 2, 3], kinds = ["r", "w", "r", "r"], holds = [5, 5, 5, 5], timeout = 3 → [5, -1, 9, 9] (писатель 1 сдаётся в момент 4, и стоявшие за ним читатели 2 и 3 сразу входят к читателю 0).
Источник: задача CodeShare