도자기 공방에 가마가 k개 있고, 1번부터 k번까지 번호가 붙어 있다. 도자기 n개가 공방에 온다. i번째 도자기는 aᵢ초에 와서 가마 앞 줄의 맨 뒤에 선다. 가마 하나는 한 번에 도자기 하나만 굽고, i번째 도자기를 한 번 굽는 데는 bᵢ초가 걸린다. i번째 도자기는 처음 cᵢ번의 굽기에서는 구울 때마다 금이 간다. 금이 간 도자기는 그 굽기가 끝난 시각부터 r초 동안 식힌 뒤 줄의 맨 뒤에 다시 선다. 그다음 굽기, 곧 cᵢ + 1번째 굽기에서는 금이 가지 않고, 그 굽기가 끝난 시각이 도자기가 완성된 시각이다. 처음에는 모든 가마가 비어 있다. 같은 시각 T에는 다음 차례로 일이 일어난다. ① T초에 굽기가 끝나는 가마가 모두 빈다. ② T초에 식힘이 끝나는 도자기들이 줄을 선다. 이런 도자기가 여럿이면 번호가 작은 가마에서 나온 것부터 선다(식히는 시간이 모두 같으니 같은 시각에 굽기가 끝난 도자기들이다). ③ T초에 오는 새 도자기들이 입력에 주어진 차례대로 줄을 선다. ④ 빈 가마와 줄 선 도자기가 모두 있는 동안, 빈 가마 가운데 번호가 가장 작은 가마가 줄 맨 앞의 도자기를 굽기 시작한다. r이 0이면 금이 간 도자기는 굽기가 끝난 바로 그 시각의 ②에서 줄을 선다. 도자기마다 완성된 시각과, 가마마다 굽기를 시작한 횟수를 출력하라.
입력
첫 줄에 도자기 수 n(1 ≤ n ≤ 10,000), 가마 수 k(1 ≤ k ≤ 8), 식히는 시간 r(0 ≤ r ≤ 1,000,000,000)이 빈칸 하나로 나뉘어 주어진다. 다음 n줄의 i번째 줄에 정수 aᵢ(0 ≤ aᵢ ≤ 1,000,000,000), bᵢ(1 ≤ bᵢ ≤ 10,000), cᵢ(0 ≤ cᵢ ≤ 10)가 빈칸 하나로 나뉘어 주어진다. aᵢ는 줄어들지 않는 차례로 주어진다(a₁ ≤ a₂ ≤ … ≤ aₙ).
출력
처음 n줄의 i번째 줄에 i번째 도자기가 완성된 시각을 출력한다. 마지막 줄에 1번 가마부터 k번 가마까지 굽기를 시작한 횟수를 빈칸 하나로 띄워 출력한다. 숫자는 쉼표 없이 출력한다.
예시 1 · stdin
4 2 3
0 2 1
0 6 0
1 3 0
5 1 0
stdout
7
6
5
7
3 2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
큐 두 개로 푸는 시뮬레이션이에요. 가마 앞의 줄이 큐인 것은 바로 보이지만, 식히는 도자기들도 큐라는 점이 핵심이에요. 식히는 시간 r이 모두 같으니 먼저 식히기 시작한 도자기가 먼저 식어요. 그래서 정렬이나 힙 없이, 금이 간 차례대로 큐에 넣고 맨 앞만 보면 돼요. 시각은 1초씩 세지 않고 '다음에 무슨 일이 일어나는 시각'으로 건너뛰어요. 새 도자기가 오는 시각, 식힘 큐 맨 앞의 식힘이 끝나는 시각, 가마 k개가 끝나는 시각 가운데 가장 이른 것이에요. 예에서는 0초에 1번·2번 도자기가 1번·2번 가마에 들어가요. 2초에 1번 도자기에 금이 가서 5초까지 식히고, 줄에 있던 3번 도자기가 1번 가마에 들어가 5초에 끝나요. 5초에는 1번 가마만 비고(2번 가마는 6초까지 구워요), 식힘을 마친 1번 도자기가 먼저, 방금 온 4번 도자기가 그다음에 줄을 서요. 그래서 1번 도자기가 1번 가마에 들어가 7초에 완성되고, 4번 도자기는 6초에 빈 2번 가마에 들어가 7초에 완성돼요. 함정 하나: 같은 시각에 식힘을 마친 도자기와 새 도자기가 겹치면 식힌 도자기가 먼저예요. 순서를 바꾸면 예에서 4번 도자기가 5초에 1번 가마를 차지해 6초에 끝나고, 1번 도자기는 6초에야 들어가 8초에 끝나요. 가마마다 구운 횟수도 4 1로 달라져요. 함정 둘: 금이 간 도자기를 식히지 않고 곧바로 줄 끝에 세우면 안 돼요. r초 뒤에야 줄에 설 수 있고, 그 사이에 온 도자기가 앞에 서요. 함정 셋: 같은 시각에는 가마를 먼저 비우고 나서 줄을 채워야 해요. 채우기를 먼저 하면 방금 끝난 가마가 다음 일이 일어날 때까지 놀아요. 함정 넷: 빈 가마가 여럿이면 번호가 작은 가마부터 써요. 완성 시각은 같아도 가마마다 구운 횟수가 달라져요. 함정 다섯: 시각은 32비트 정수를 넘어요. 1,000,000,000초에 온 도자기가 1,000,000,000초씩 열 번 식으면 110억을 넘어요. C와 C++은 long long, Java와 C#은 long을 써야 하고, Python 정수와 JavaScript·TypeScript·크레이콘의 수(2^53까지 정확)는 그대로 괜찮아요. 함정 여섯: 줄에는 도자기가 모두 합쳐 110,000번까지 들어가요. 크레이콘의 목록은 10,000칸까지라 넣기만 하는 목록으로는 큐를 만들 수 없어요. 줄에 동시에 서 있는 도자기는 n개를 넘지 않으니 n칸짜리 목록을 둥글게 돌려 쓰고, 자리를 n으로 나눈 나머지로 감아야 해요. 감지 않으면 목록 밖을 가리켜 멈춰요. 큐를 쓰는 방법은 언어마다 달라요. Python은 collections.deque의 append와 popleft를 써요. 리스트의 pop(0)은 뒤의 원소를 모두 당겨서 느려요. Java는 ArrayDeque, C#은 Queue<int>, C++은 std::queue를 써요. JavaScript와 TypeScript에는 큐가 따로 없어서 배열과 머리 번호로 만들었어요. shift()는 배열이 길면 느려질 수 있어요. C는 배열과 머리 번호, 개수로 둥근 큐를 직접 만들어요. 크레이콘도 새목록(n, 0)으로 만든 목록을 같은 방식으로 써요.
Pythonmain.py · 58 줄
import sysfrom collections import dequedata = sys.stdin.buffer.read().split()n, k, rest = int(data[0]), int(data[1]), int(data[2])arrive = [int(data[3 + 3 * i]) for i in range(n)]bake = [int(data[4 + 3 * i]) for i in range(n)]left = [int(data[5 + 3 * i]) for i in range(n)] # 앞으로 금이 갈 횟수end = [-1] * k # 가마가 굽기를 끝내는 시각(-1이면 비어 있다)cur = [0] * k # 가마가 굽고 있는 도자기count = [0] * k # 가마마다 구운 횟수ready = [0] * n # 식힘이 끝나 다시 줄에 서는 시각finish = [0] * ncooling = deque() # 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다line = deque() # 가마 앞의 줄nxt = 0 # 아직 오지 않은 첫 도자기done = 0while done < n: # 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 t = -1 if nxt < n: t = arrive[nxt] if cooling and (t < 0 or ready[cooling[0]] < t): t = ready[cooling[0]] for j in range(k): if end[j] >= 0 and (t < 0 or end[j] < t): t = end[j] # ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) for j in range(k): if end[j] == t: i = cur[j] end[j] = -1 if left[i] > 0: left[i] -= 1 ready[i] = t + rest cooling.append(i) else: finish[i] = t done += 1 # ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 while cooling and ready[cooling[0]] == t: line.append(cooling.popleft()) while nxt < n and arrive[nxt] == t: line.append(nxt) nxt += 1 # ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 for j in range(k): if not line: break if end[j] < 0: i = line.popleft() cur[j] = i end[j] = t + bake[i] count[j] += 1print("\n".join(map(str, finish)))print(" ".join(map(str, count)))
JavaScriptmain.js · 73 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, k, rest] = data;const arrive = [];const bake = [];const left = []; // 앞으로 금이 갈 횟수for (let i = 0; i < n; i++) { arrive.push(data[3 + 3 * i]); bake.push(data[4 + 3 * i]); left.push(data[5 + 3 * i]);}// 큐: 배열과 머리 번호. shift()는 뒤의 것을 모두 당기니 머리 번호만 옮긴다class Queue { constructor() { this.items = []; this.head = 0; } get size() { return this.items.length - this.head; } front() { return this.items[this.head]; } push(x) { this.items.push(x); } pop() { return this.items[this.head++]; }}const end = new Array(k).fill(-1); // 가마가 굽기를 끝내는 시각(-1이면 비어 있다)const cur = new Array(k).fill(0); // 가마가 굽고 있는 도자기const count = new Array(k).fill(0); // 가마마다 구운 횟수const ready = new Array(n).fill(0); // 식힘이 끝나 다시 줄에 서는 시각const finish = new Array(n).fill(0);const cooling = new Queue(); // 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다const line = new Queue(); // 가마 앞의 줄let next = 0; // 아직 오지 않은 첫 도자기let done = 0;while (done < n) { // 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 let t = Infinity; if (next < n) t = arrive[next]; if (cooling.size > 0) t = Math.min(t, ready[cooling.front()]); for (let j = 0; j < k; j++) if (end[j] >= 0) t = Math.min(t, end[j]); // ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) for (let j = 0; j < k; j++) { if (end[j] !== t) continue; const i = cur[j]; end[j] = -1; if (left[i] > 0) { left[i]--; ready[i] = t + rest; cooling.push(i); } else { finish[i] = t; done++; } } // ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 while (cooling.size > 0 && ready[cooling.front()] === t) line.push(cooling.pop()); while (next < n && arrive[next] === t) line.push(next++); // ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 for (let j = 0; j < k && line.size > 0; j++) { if (end[j] >= 0) continue; const i = line.pop(); cur[j] = i; end[j] = t + bake[i]; count[j]++; }}console.log(finish.join("\n") + "\n" + count.join(" "));
TypeScriptmain.ts · 73 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, k, rest] = data;const arrive: number[] = [];const bake: number[] = [];const left: number[] = []; // 앞으로 금이 갈 횟수for (let i = 0; i < n; i++) { arrive.push(data[3 + 3 * i]); bake.push(data[4 + 3 * i]); left.push(data[5 + 3 * i]);}// 큐: 배열과 머리 번호. shift()는 뒤의 것을 모두 당기니 머리 번호만 옮긴다class Queue<T> { private readonly items: T[] = []; private head = 0; get size(): number { return this.items.length - this.head; } front(): T { return this.items[this.head]; } push(x: T): void { this.items.push(x); } pop(): T { return this.items[this.head++]; }}const end: number[] = new Array<number>(k).fill(-1); // 가마가 굽기를 끝내는 시각(-1이면 비어 있다)const cur: number[] = new Array<number>(k).fill(0); // 가마가 굽고 있는 도자기const count: number[] = new Array<number>(k).fill(0); // 가마마다 구운 횟수const ready: number[] = new Array<number>(n).fill(0); // 식힘이 끝나 다시 줄에 서는 시각const finish: number[] = new Array<number>(n).fill(0);const cooling = new Queue<number>(); // 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다const line = new Queue<number>(); // 가마 앞의 줄let next = 0; // 아직 오지 않은 첫 도자기let done = 0;while (done < n) { // 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 let t = Infinity; if (next < n) t = arrive[next]; if (cooling.size > 0) t = Math.min(t, ready[cooling.front()]); for (let j = 0; j < k; j++) if (end[j] >= 0) t = Math.min(t, end[j]); // ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) for (let j = 0; j < k; j++) { if (end[j] !== t) continue; const i: number = cur[j]; end[j] = -1; if (left[i] > 0) { left[i]--; ready[i] = t + rest; cooling.push(i); } else { finish[i] = t; done++; } } // ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 while (cooling.size > 0 && ready[cooling.front()] === t) line.push(cooling.pop()); while (next < n && arrive[next] === t) line.push(next++); // ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 for (let j = 0; j < k && line.size > 0; j++) { if (end[j] >= 0) continue; const i: number = line.pop(); cur[j] = i; end[j] = t + bake[i]; count[j]++; }}console.log(finish.join("\n") + "\n" + count.join(" "));
JavaMain.java · 65 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int k = (int) st.nval; st.nextToken(); long rest = (long) st.nval; long[] arrive = new long[n]; int[] bake = new int[n], left = new int[n]; // left: 앞으로 금이 갈 횟수 for (int i = 0; i < n; i++) { st.nextToken(); arrive[i] = (long) st.nval; st.nextToken(); bake[i] = (int) st.nval; st.nextToken(); left[i] = (int) st.nval; } long[] end = new long[k]; // 가마가 굽기를 끝내는 시각(-1이면 비어 있다). 시각은 int를 넘는다 Arrays.fill(end, -1); int[] cur = new int[k]; // 가마가 굽고 있는 도자기 int[] count = new int[k]; // 가마마다 구운 횟수 long[] ready = new long[n]; // 식힘이 끝나 다시 줄에 서는 시각 long[] finish = new long[n]; ArrayDeque<Integer> cooling = new ArrayDeque<>(); // 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다 ArrayDeque<Integer> line = new ArrayDeque<>(); // 가마 앞의 줄 int next = 0, done = 0; while (done < n) { // 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 long t = Long.MAX_VALUE; if (next < n) t = arrive[next]; if (!cooling.isEmpty()) t = Math.min(t, ready[cooling.peekFirst()]); for (int j = 0; j < k; j++) if (end[j] >= 0) t = Math.min(t, end[j]); // ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) for (int j = 0; j < k; j++) { if (end[j] != t) continue; int i = cur[j]; end[j] = -1; if (left[i] > 0) { left[i]--; ready[i] = t + rest; cooling.addLast(i); } else { finish[i] = t; done++; } } // ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 while (!cooling.isEmpty() && ready[cooling.peekFirst()] == t) line.addLast(cooling.pollFirst()); while (next < n && arrive[next] == t) line.addLast(next++); // ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 for (int j = 0; j < k && !line.isEmpty(); j++) { if (end[j] >= 0) continue; int i = line.pollFirst(); cur[j] = i; end[j] = t + bake[i]; count[j]++; } } StringBuilder sb = new StringBuilder(); for (long x : finish) sb.append(x).append('\n'); for (int j = 0; j < k; j++) sb.append(j > 0 ? " " : "").append(count[j]); System.out.println(sb); }}
C#Main.cs · 75 줄
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]), k = int.Parse(data[1]); long rest = long.Parse(data[2]); var arrive = new long[n]; var bake = new int[n]; var left = new int[n]; // 앞으로 금이 갈 횟수 for (int i = 0; i < n; i++) { arrive[i] = long.Parse(data[3 + 3 * i]); bake[i] = int.Parse(data[4 + 3 * i]); left[i] = int.Parse(data[5 + 3 * i]); } var end = new long[k]; // 가마가 굽기를 끝내는 시각(-1이면 비어 있다). 시각은 int를 넘는다 Array.Fill(end, -1L); var cur = new int[k]; // 가마가 굽고 있는 도자기 var count = new int[k]; // 가마마다 구운 횟수 var ready = new long[n]; // 식힘이 끝나 다시 줄에 서는 시각 var finish = new long[n]; var cooling = new Queue<int>(); // 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다 var line = new Queue<int>(); // 가마 앞의 줄 int next = 0, done = 0; while (done < n) { // 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 long t = long.MaxValue; if (next < n) t = arrive[next]; if (cooling.Count > 0) t = Math.Min(t, ready[cooling.Peek()]); for (int j = 0; j < k; j++) if (end[j] >= 0) t = Math.Min(t, end[j]); // ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) for (int j = 0; j < k; j++) { if (end[j] != t) continue; int i = cur[j]; end[j] = -1; if (left[i] > 0) { left[i]--; ready[i] = t + rest; cooling.Enqueue(i); } else { finish[i] = t; done++; } } // ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 while (cooling.Count > 0 && ready[cooling.Peek()] == t) line.Enqueue(cooling.Dequeue()); while (next < n && arrive[next] == t) line.Enqueue(next++); // ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 for (int j = 0; j < k && line.Count > 0; j++) { if (end[j] >= 0) continue; int i = line.Dequeue(); cur[j] = i; end[j] = t + bake[i]; count[j]++; } } var sb = new StringBuilder(); foreach (long x in finish) sb.Append(x).Append('\n'); sb.Append(string.Join(" ", count)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 67 줄
#include <algorithm>#include <iostream>#include <queue>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; long long rest; cin >> n >> k >> rest; vector<long long> arrive(n); vector<int> bake(n), left(n); // left: 앞으로 금이 갈 횟수 for (int i = 0; i < n; i++) cin >> arrive[i] >> bake[i] >> left[i]; vector<long long> end(k, -1); // 가마가 굽기를 끝내는 시각(-1이면 비어 있다). 시각은 int를 넘는다 vector<int> cur(k, 0); // 가마가 굽고 있는 도자기 vector<int> count(k, 0); // 가마마다 구운 횟수 vector<long long> ready(n, 0); // 식힘이 끝나 다시 줄에 서는 시각 vector<long long> finish(n, 0); queue<int> cooling; // 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다 queue<int> line; // 가마 앞의 줄 int next = 0, done = 0; while (done < n) { // 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 long long t = -1; if (next < n) t = arrive[next]; if (!cooling.empty() && (t < 0 || ready[cooling.front()] < t)) t = ready[cooling.front()]; for (int j = 0; j < k; j++) if (end[j] >= 0 && (t < 0 || end[j] < t)) t = end[j]; // ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) for (int j = 0; j < k; j++) { if (end[j] != t) continue; int i = cur[j]; end[j] = -1; if (left[i] > 0) { left[i]--; ready[i] = t + rest; cooling.push(i); } else { finish[i] = t; done++; } } // ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 while (!cooling.empty() && ready[cooling.front()] == t) { line.push(cooling.front()); cooling.pop(); } while (next < n && arrive[next] == t) line.push(next++); // ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 for (int j = 0; j < k && !line.empty(); j++) { if (end[j] >= 0) continue; int i = line.front(); line.pop(); cur[j] = i; end[j] = t + bake[i]; count[j]++; } } for (long long x : finish) cout << x << '\n'; for (int j = 0; j < k; j++) cout << (j ? " " : "") << count[j]; cout << '\n'; return 0;}
Cmain.c · 82 줄
#include <stdio.h>#define MAXN 10000#define MAXK 8static long long arrive[MAXN], ready[MAXN], finish[MAXN];static int bake[MAXN], left[MAXN]; /* left: 앞으로 금이 갈 횟수 *//* 큐: 둥근 배열. 한 번에 n개보다 많이 들어 있지 않으니 MAXN칸을 돌려 쓴다 */typedef struct { int items[MAXN]; int head, size;} Queue;static void push(Queue *q, int x) { q->items[(q->head + q->size) % MAXN] = x; q->size++;}static int pop(Queue *q) { int x = q->items[q->head]; q->head = (q->head + 1) % MAXN; q->size--; return x;}static Queue cooling; /* 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다 */static Queue line; /* 가마 앞의 줄 */int main(void) { int n, k; long long rest; if (scanf("%d %d %lld", &n, &k, &rest) != 3) return 1; for (int i = 0; i < n; i++) scanf("%lld %d %d", &arrive[i], &bake[i], &left[i]); long long end[MAXK]; /* 가마가 굽기를 끝내는 시각(-1이면 비어 있다). 시각은 int를 넘는다 */ int cur[MAXK], count[MAXK]; for (int j = 0; j < k; j++) { end[j] = -1; cur[j] = 0; count[j] = 0; } int next = 0, done = 0; while (done < n) { /* 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 */ long long t = -1; if (next < n) t = arrive[next]; if (cooling.size > 0 && (t < 0 || ready[cooling.items[cooling.head]] < t)) t = ready[cooling.items[cooling.head]]; for (int j = 0; j < k; j++) if (end[j] >= 0 && (t < 0 || end[j] < t)) t = end[j]; /* ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) */ for (int j = 0; j < k; j++) { if (end[j] != t) continue; int i = cur[j]; end[j] = -1; if (left[i] > 0) { left[i]--; ready[i] = t + rest; push(&cooling, i); } else { finish[i] = t; done++; } } /* ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 */ while (cooling.size > 0 && ready[cooling.items[cooling.head]] == t) push(&line, pop(&cooling)); while (next < n && arrive[next] == t) push(&line, next++); /* ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 */ for (int j = 0; j < k && line.size > 0; j++) { if (end[j] >= 0) continue; int i = pop(&line); cur[j] = i; end[j] = t + bake[i]; count[j]++; } } for (int i = 0; i < n; i++) printf("%lld\n", finish[i]); for (int j = 0; j < k; j++) printf(j ? " %d" : "%d", count[j]); printf("\n"); return 0;}
Craykonmain.cray · 106 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];k = 첫줄[1];rest = 첫줄[2];arrive = [];bake = [];left = []; // 앞으로 금이 갈 횟수반복 (i = 0; i < n; i++){ 줄 = 콘솔.수들읽기(); arrive.넣기(줄[0]); bake.넣기(줄[1]); left.넣기(줄[2]);}end = 새목록(k, -1); // 가마가 굽기를 끝내는 시각(-1이면 비어 있다)cur = 새목록(k, 0); // 가마가 굽고 있는 도자기count = 새목록(k, 0); // 가마마다 구운 횟수ready = 새목록(n, 0); // 식힘이 끝나 다시 줄에 서는 시각finish = 새목록(n, 0);// 큐 두 개를 둥근 목록으로 만든다. 목록은 10,000칸까지라 끝없이 넣기만 할 수 없고,// 한 번에 n개보다 많이 들어 있지 않으니 n칸을 돌려 쓴다cooling = 새목록(n, 0); // 식히는 도자기: 넣은 차례가 곧 식힘이 끝나는 차례다coolHead = 0;coolSize = 0;line = 새목록(n, 0); // 가마 앞의 줄lineHead = 0;lineSize = 0;next = 0; // 아직 오지 않은 첫 도자기done = 0;동안 (done < n){ // 다음에 무엇인가 일어나는 시각: 새 도자기, 식힘 끝, 굽기 끝 가운데 가장 이른 것 t = -1; 만약 (next < n) { t = arrive[next]; } 만약 (coolSize > 0 && (t < 0 || ready[cooling[coolHead]] < t)) { t = ready[cooling[coolHead]]; } 반복 (j = 0; j < k; j++) { 만약 (end[j] >= 0 && (t < 0 || end[j] < t)) { t = end[j]; } } // ① 굽기가 끝난 가마가 빈다(번호가 작은 가마부터) 반복 (j = 0; j < k; j++) { 만약 (end[j] == t) { i = cur[j]; end[j] = -1; 만약 (left[i] > 0) { left[i] -= 1; ready[i] = t + rest; cooling[(coolHead + coolSize) % n] = i; coolSize += 1; } 아니면 { finish[i] = t; done += 1; } } } // ②③ 식힘을 마친 도자기가 먼저, 새로 온 도자기가 그다음에 줄을 선다 동안 (coolSize > 0 && ready[cooling[coolHead]] == t) { line[(lineHead + lineSize) % n] = cooling[coolHead]; lineSize += 1; coolHead = (coolHead + 1) % n; coolSize -= 1; } 동안 (next < n && arrive[next] == t) { line[(lineHead + lineSize) % n] = next; lineSize += 1; next += 1; } // ④ 번호가 작은 빈 가마부터 줄 맨 앞 도자기를 굽는다 반복 (j = 0; j < k && lineSize > 0; j++) { 만약 (end[j] < 0) { i = line[lineHead]; lineHead = (lineHead + 1) % n; lineSize -= 1; cur[j] = i; end[j] = t + bake[i]; count[j] += 1; } }}각각 (x 에서 finish){ 콘솔.쓰기(x);}콘솔.쓰기(count.잇기(" "));