A bike rental shop has n bikes numbered 1 to n.
Bike i has been ridden a distance of wᵢ so far.
q customers come in order. They come one at a time, and the next customer comes after the previous one has returned the bike.
Each time a customer comes, the shop lends the bike with the shortest distance ridden among the bikes that remain.
If several bikes have the same distance, it lends the one with the smallest number.
The j-th customer rides dⱼ and returns the bike, and that bike's distance grows by dⱼ.
If the distance of a returned bike is L or more, the bike is sent to the repair shop and is never lent again.
If no bike remains when a customer comes, that customer cannot borrow a bike.
For each customer print on one line the number of the bike borrowed. Print 0 for a customer who could not borrow one.
On the last line print the number of bikes sent to the repair shop.
Input
The first line has n, q and L separated by single spaces. The second line has w₁ … wₙ and the third line d₁ … d_q, separated by single spaces. 1 ≤ n ≤ 10,000, 1 ≤ q ≤ 10,000, 1 ≤ L ≤ 1,000,000,000,000, 0 ≤ wᵢ < L, 1 ≤ dⱼ ≤ 1,000,000,000. All are integers
Output
q lines with the bike number for each customer (0 if none could be borrowed), then one line with the number of bikes sent to the repair shop
Example 1 · stdin
3 7 10
4 2 2
3 3 5 4 2 6 1
stdout
2
3
1
2
3
3
1
2
Example 2 · stdin
1 3 5
0
5 1 1
stdout
1
0
0
1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
A heap (priority queue) is what you use when you keep taking out the smallest item, changing it and putting it back. Scanning all bikes for every customer takes n × q steps, while a heap needs about log n per operation. In the first example bikes 2 and 3 are both at 5 when the fourth customer comes, so bike 2 goes out; bike 1, ridden by the seventh customer, reaches 9 + 1 = 10, exactly L, and goes to repair. Trap one: on equal distance the smaller number wins. A heap does not keep any order among equal values, so the number must be part of the comparison. Python pushes (distance, number) tuples to heapq and C++ pushes a pair to priority_queue; both compare from the first element. C++ priority_queue gives the largest first, so pass greater to get the smallest first. C# gives a tuple priority, as in PriorityQueue<int, (long, int)>. Trap two: writing the comparator of Java's PriorityQueue as a subtraction like (int) (a[0] - b[0]) is wrong. When the difference exceeds about 2.1 billion, cutting it to int flips the sign. Use Long.compare. Trap three: distances can exceed one trillion, so C and C++ need long long and Java and C# need long. An int corrupts the value. Python integers have no limit, and numbers in JavaScript, TypeScript and Craykon are exact up to 2^53 (about 9 quadrillion), so they can be used as they are. Trap four: it is L or more. A bike that reaches exactly L also goes to repair. Trap five: sorting once at the start and lending in that order round and round is wrong. After a ride the distance changes and so does the order. Trap six: the bikes can run out. Check for an empty heap before taking from it. Python heappop raises IndexError, Java poll returns null, C++ top is undefined behaviour, and C# TryDequeue returns false. JavaScript, TypeScript, C and Craykon have no heap, so those solutions build one on an array. They store only bike numbers in the heap and look into the distance array when comparing. A bike's distance is never changed while it is inside the heap; it is changed after the bike is taken out and before it is pushed again, so the heap stays valid. Craykon adds to a list with Add and sifts up, and removes the last item with RemoveAt, puts it on top and sifts down.
Pythonmain.py · 26 lines
import heapqimport sysdata = sys.stdin.read().split()n, q, limit = int(data[0]), int(data[1]), int(data[2])# 힙에 (달린 거리, 번호) 튜플을 넣는다: 튜플은 앞에서부터 견주니 거리가 같으면 번호가 작은 것이 위로 온다heap = [(int(data[3 + i]), i + 1) for i in range(n)]heapq.heapify(heap)out = []repaired = 0for j in range(q): d = int(data[3 + n + j]) if not heap: # 빌려줄 자전거가 없다 out.append("0") continue dist, bike = heapq.heappop(heap) out.append(str(bike)) dist += d if dist >= limit: # 딱 L이 되어도 정비소로 간다 repaired += 1 else: heapq.heappush(heap, (dist, bike))out.append(str(repaired))print("\n".join(out))
JavaScriptmain.js · 58 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, limit] = data;// JavaScript에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다const dist = [0, ...data.slice(3, 3 + n)];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽const before = (a, b) => dist[a] < dist[b] || (dist[a] === dist[b] && a < b);const heap = [];function push(b) { heap.push(b); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!before(heap[i], heap[parent])) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop() { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let first = i; if (l < heap.length && before(heap[l], heap[first])) first = l; if (r < heap.length && before(heap[r], heap[first])) first = r; if (first === i) break; [heap[i], heap[first]] = [heap[first], heap[i]]; i = first; } } return top;}for (let b = 1; b <= n; b++) push(b);const out = [];let repaired = 0;for (let j = 0; j < q; j++) { const d = data[3 + n + j]; if (heap.length === 0) { out.push(0); // 빌려줄 자전거가 없다 continue; } const bike = pop(); out.push(bike); dist[bike] += d; // 10^12 남짓이라 number로도 정확하다 if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike);}out.push(repaired);console.log(out.join("\n"));
TypeScriptmain.ts · 60 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, limit] = data;// TypeScript에도 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다const dist: number[] = [0, ...data.slice(3, 3 + n)];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽const before = (a: number, b: number): boolean => dist[a] < dist[b] || (dist[a] === dist[b] && a < b);const heap: number[] = [];function push(b: number): void { heap.push(b); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!before(heap[i], heap[parent])) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop(): number { const top = heap[0]; const last = heap.pop() as number; if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let first = i; if (l < heap.length && before(heap[l], heap[first])) first = l; if (r < heap.length && before(heap[r], heap[first])) first = r; if (first === i) break; [heap[i], heap[first]] = [heap[first], heap[i]]; i = first; } } return top;}for (let b = 1; b <= n; b++) push(b);const out: number[] = [];let repaired = 0;for (let j = 0; j < q; j++) { const d = data[3 + n + j]; if (heap.length === 0) { out.push(0); // 빌려줄 자전거가 없다 continue; } const bike = pop(); out.push(bike); dist[bike] += d; // 10^12 남짓이라 number로도 정확하다 if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike);}out.push(repaired);console.log(out.join("\n"));
JavaMain.java · 36 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long limit = Long.parseLong(st.nextToken()); // 10^12까지라 long // {달린 거리, 번호}를 넣는다. 거리가 짧은 것, 같으면 번호가 작은 것이 먼저 — 뺄셈이 아니라 Long.compare로 견준다 PriorityQueue<long[]> heap = new PriorityQueue<>( (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])); st = new StringTokenizer(br.readLine()); for (int b = 1; b <= n; b++) heap.add(new long[] {Long.parseLong(st.nextToken()), b}); StringBuilder sb = new StringBuilder(); int repaired = 0; st = new StringTokenizer(br.readLine()); for (int j = 0; j < q; j++) { long d = Long.parseLong(st.nextToken()); if (heap.isEmpty()) { // 빌려줄 자전거가 없다 sb.append("0\n"); continue; } long[] top = heap.poll(); sb.append(top[1]).append('\n'); top[0] += d; if (top[0] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.add(top); } sb.append(repaired).append('\n'); System.out.print(sb); }}
C#Main.cs · 37 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), q = int.Parse(data[1]); long limit = long.Parse(data[2]); // 10^12까지라 long // PriorityQueue<값, 우선순위>: 우선순위가 작은 것이 먼저 나온다 // 우선순위를 (달린 거리, 번호) 튜플로 주면 거리가 같을 때 번호가 작은 것이 먼저다 var heap = new PriorityQueue<int, (long, int)>(); for (int b = 1; b <= n; b++) heap.Enqueue(b, (long.Parse(data[2 + b]), b)); var sb = new StringBuilder(); int repaired = 0; for (int j = 0; j < q; j++) { long d = long.Parse(data[3 + n + j]); // TryDequeue는 비어 있으면 false를 돌려준다: 빌려줄 자전거가 없다 if (!heap.TryDequeue(out int bike, out (long dist, int id) key)) { sb.Append("0\n"); continue; } sb.Append(bike).Append('\n'); long dist = key.dist + d; if (dist >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.Enqueue(bike, (dist, bike)); } sb.Append(repaired).Append('\n'); Console.Write(sb); }}
C++main.cpp · 42 lines
#include <functional>#include <iostream>#include <queue>#include <utility>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; long long limit; // 10^12까지라 long long cin >> n >> q >> limit; // priority_queue는 기본이 큰 것 먼저다: greater를 주어 작은 것이 먼저 나오게 한다 // pair는 first부터 견주니 (달린 거리, 번호)로 넣으면 거리가 같을 때 번호가 작은 것이 먼저다 typedef pair<long long, int> Bike; priority_queue<Bike, vector<Bike>, greater<Bike>> heap; for (int b = 1; b <= n; b++) { long long w; cin >> w; heap.push({w, b}); } int repaired = 0; for (int j = 0; j < q; j++) { long long d; cin >> d; if (heap.empty()) { // 빌려줄 자전거가 없다 cout << "0\n"; continue; } Bike top = heap.top(); heap.pop(); cout << top.second << '\n'; top.first += d; if (top.first >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else heap.push(top); } cout << repaired << '\n'; return 0;}
Cmain.c · 69 lines
#include <stdio.h>#include <stdlib.h>// C에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다static long long *dist;static int *heap;static int size = 0;// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽static int before(int a, int b) { return dist[a] < dist[b] || (dist[a] == dist[b] && a < b);}static void push(int b) { int i = size++; heap[i] = b; while (i > 0) { int parent = (i - 1) / 2; if (!before(heap[i], heap[parent])) break; int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t; i = parent; }}static int pop(void) { int top = heap[0]; heap[0] = heap[--size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, first = i; if (l < size && before(heap[l], heap[first])) first = l; if (r < size && before(heap[r], heap[first])) first = r; if (first == i) break; int t = heap[i]; heap[i] = heap[first]; heap[first] = t; i = first; } return top;}int main(void) { int n, q; long long limit; // 10^12까지라 int에는 안 든다 if (scanf("%d %d %lld", &n, &q, &limit) != 3) return 0; dist = malloc((n + 1) * sizeof(long long)); heap = malloc((n + 1) * sizeof(int)); for (int b = 1; b <= n; b++) { scanf("%lld", &dist[b]); push(b); } int repaired = 0; for (int j = 0; j < q; j++) { long long d; scanf("%lld", &d); if (size == 0) { // 빌려줄 자전거가 없다 printf("0\n"); continue; } int bike = pop(); printf("%d\n", bike); dist[bike] += d; if (dist[bike] >= limit) repaired++; // 딱 L이 되어도 정비소로 간다 else push(bike); } printf("%d\n", repaired); free(dist); free(heap); return 0;}
Craykonmain.cray · 94 lines
// 크레이콘에는 힙이 없어서 직접 만든다. dist[b] = b번 자전거가 달린 거리, heap에는 번호만 넣는다(번호는 0부터)첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];limit = 첫줄[2];dist = Console.ReadNumbers();타는거리 = Console.ReadNumbers();heap = [];// a번이 b번보다 먼저 나가야 하는가: 거리가 짧은 쪽, 같으면 번호가 작은 쪽먼저인가(a, b){ return dist[a] < dist[b] || dist[a] == dist[b] && a < b;}힙넣기(b){ heap.Add(b); i = heap.Count - 1; while (i > 0) { 부모 = Mathf.Quot(i - 1, 2); if (!먼저인가(heap[i], heap[부모])) { break; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }}힙빼기(){ top = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); i = 0; while (true) { l = 2 * i + 1; r = l + 1; first = i; if (l < heap.Count && 먼저인가(heap[l], heap[first])) { first = l; } if (r < heap.Count && 먼저인가(heap[r], heap[first])) { first = r; } if (first == i) { break; } t = heap[i]; heap[i] = heap[first]; heap[first] = t; i = first; } return top;}for (b = 0; b < n; b++){ 힙넣기(b);}out = [];repaired = 0;foreach (d in 타는거리){ if (heap.Count == 0) { out.Add(0); // 빌려줄 자전거가 없다 } else { bike = 힙빼기(); out.Add(bike + 1); dist[bike] += d; if (dist[bike] >= limit) { repaired += 1; } else { 힙넣기(bike); } }}Console.WriteLine(out.Join("\n"));Console.WriteLine(repaired);