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.つなぐ(" "));