順番に働く CPU

import sysfrom collections import deque data = list(map(int, sys.stdin.read().split()))n, q = data[0], data[1]arrive = data[2::2]left = data[3::2]  # 남은 일 finish = [0] * nline = deque()t = 0nxt = 0  # 아직 줄에 서지 않은 첫 프로세스done = 0  def join_until(now):    """now까지 도착한 프로세스를 번호 차례로 줄에 세운다."""    global nxt    while nxt < n and arrive[nxt] <= now:        line.append(nxt)        nxt += 1  while done < n:    if not line:  # 줄이 비면 다음 프로세스가 올 때까지 쉰다        t = max(t, arrive[nxt])        join_until(t)    p = line.popleft()    run = min(q, left[p])    t += run    left[p] -= run    join_until(t)  # 이 시각까지 온 프로세스가 먼저 줄에 서고    if left[p] > 0:        line.append(p)  # 그 뒤에 방금 돈 프로세스가 선다    else:        finish[p] = t        done += 1print(" ".join(map(str, finish)))

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = data;const arrive = [];const left = []; // 남은 일for (let i = 0; i < n; i++) {  arrive.push(data[2 + 2 * i]);  left.push(data[3 + 2 * i]);} // 배열 + 앞 자리(head)로 큐를 만든다. shift()는 뒤의 것을 모두 당긴다.const line = [];let head = 0;const finish = new Array(n).fill(0);let t = 0;let next = 0; // 아직 줄에 서지 않은 첫 프로세스let done = 0; // now까지 도착한 프로세스를 번호 차례로 줄에 세운다function joinUntil(now) {  while (next < n && arrive[next] <= now) line.push(next++);} while (done < n) {  if (head === line.length) {    // 줄이 비면 다음 프로세스가 올 때까지 쉰다    t = Math.max(t, arrive[next]);    joinUntil(t);  }  const p = line[head++];  const run = Math.min(q, left[p]);  t += run;  left[p] -= run;  joinUntil(t); // 이 시각까지 온 프로세스가 먼저 줄에 서고  if (left[p] > 0) line.push(p); // 그 뒤에 방금 돈 프로세스가 선다  else {    finish[p] = t;    done++;  }}console.log(finish.join(" "));

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = data;const arrive: number[] = [];const left: number[] = []; // 남은 일for (let i = 0; i < n; i++) {  arrive.push(data[2 + 2 * i]);  left.push(data[3 + 2 * i]);} // 배열 + 앞 자리(head)로 큐를 만든다. shift()는 뒤의 것을 모두 당긴다.const line: number[] = [];let head = 0;const finish: number[] = new Array<number>(n).fill(0);let t = 0;let next = 0; // 아직 줄에 서지 않은 첫 프로세스let done = 0; // now까지 도착한 프로세스를 번호 차례로 줄에 세운다function joinUntil(now: number): void {  while (next < n && arrive[next] <= now) line.push(next++);} while (done < n) {  if (head === line.length) {    // 줄이 비면 다음 프로세스가 올 때까지 쉰다    t = Math.max(t, arrive[next]);    joinUntil(t);  }  const p = line[head++];  const run = Math.min(q, left[p]);  t += run;  left[p] -= run;  joinUntil(t); // 이 시각까지 온 프로세스가 먼저 줄에 서고  if (left[p] > 0) line.push(p); // 그 뒤에 방금 돈 프로세스가 선다  else {    finish[p] = t;    done++;  }}console.log(finish.join(" "));

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.StringTokenizer; public class Main {    static int n, next = 0; // next: 아직 줄에 서지 않은 첫 프로세스    static long[] arrive;    static ArrayDeque<Integer> line = new ArrayDeque<>();     // now까지 도착한 프로세스를 번호 차례로 줄에 세운다    static void joinUntil(long now) {        while (next < n && arrive[next] <= now) line.addLast(next++);    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(in.readLine());        n = Integer.parseInt(st.nextToken());        long q = Long.parseLong(st.nextToken());        arrive = new long[n];        long[] left = new long[n]; // 남은 일        for (int i = 0; i < n; i++) {            st = new StringTokenizer(in.readLine());            arrive[i] = Long.parseLong(st.nextToken());            left[i] = Long.parseLong(st.nextToken());        }         long[] finish = new long[n];        long t = 0; // 5×10¹²까지 가서 long        int done = 0;        while (done < n) {            if (line.isEmpty()) { // 줄이 비면 다음 프로세스가 올 때까지 쉰다                t = Math.max(t, arrive[next]);                joinUntil(t);            }            int p = line.pollFirst();            long run = Math.min(q, left[p]);            t += run;            left[p] -= run;            joinUntil(t); // 이 시각까지 온 프로세스가 먼저 줄에 서고            if (left[p] > 0) line.addLast(p); // 그 뒤에 방금 돈 프로세스가 선다            else {                finish[p] = t;                done++;            }        }        StringBuilder out = new StringBuilder();        for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(finish[i]);        System.out.println(out);    }}

using System;using System.Collections.Generic; class Program{    static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(first[0]);        long q = long.Parse(first[1]);        long[] arrive = new long[n];        long[] left = new long[n]; // 남은 일        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            arrive[i] = long.Parse(p[0]);            left[i] = long.Parse(p[1]);        }         var line = new Queue<int>();        int next = 0; // 아직 줄에 서지 않은 첫 프로세스        // now까지 도착한 프로세스를 번호 차례로 줄에 세운다        void JoinUntil(long now)        {            while (next < n && arrive[next] <= now) line.Enqueue(next++);        }         long[] finish = new long[n];        long t = 0; // 5×10¹²까지 가서 long        int done = 0;        while (done < n)        {            if (line.Count == 0) // 줄이 비면 다음 프로세스가 올 때까지 쉰다            {                t = Math.Max(t, arrive[next]);                JoinUntil(t);            }            int p = line.Dequeue();            long run = Math.Min(q, left[p]);            t += run;            left[p] -= run;            JoinUntil(t); // 이 시각까지 온 프로세스가 먼저 줄에 서고            if (left[p] > 0) line.Enqueue(p); // 그 뒤에 방금 돈 프로세스가 선다            else            {                finish[p] = t;                done++;            }        }        Console.WriteLine(string.Join(" ", finish));    }}

#include <algorithm>#include <iostream>#include <queue>#include <vector> int main() {    int n;    long long q;    std::cin >> n >> q;    std::vector<long long> arrive(n), left(n); // left: 남은 일    for (int i = 0; i < n; i++) std::cin >> arrive[i] >> left[i];     std::queue<int> line;    int next = 0; // 아직 줄에 서지 않은 첫 프로세스    // now까지 도착한 프로세스를 번호 차례로 줄에 세운다    auto joinUntil = [&](long long now) {        while (next < n && arrive[next] <= now) line.push(next++);    };     std::vector<long long> finish(n);    long long t = 0; // 5×10¹²까지 가서 long long    int done = 0;    while (done < n) {        if (line.empty()) { // 줄이 비면 다음 프로세스가 올 때까지 쉰다            t = std::max(t, arrive[next]);            joinUntil(t);        }        int p = line.front(); // pop()은 값을 돌려주지 않아서 front()를 먼저 읽는다        line.pop();        long long run = std::min(q, left[p]);        t += run;        left[p] -= run;        joinUntil(t); // 이 시각까지 온 프로세스가 먼저 줄에 서고        if (left[p] > 0) line.push(p); // 그 뒤에 방금 돈 프로세스가 선다        else {            finish[p] = t;            done++;        }    }    for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << finish[i];    std::cout << "\n";}

#include <stdio.h> #define MAXN 5000 static long long arrive[MAXN], left[MAXN], finish[MAXN];/* 크기 MAXN인 원형 큐: 줄에는 많아야 n개만 있다 */static int line[MAXN];static int head = 0, size = 0;static int n, next = 0; /* next: 아직 줄에 서지 않은 첫 프로세스 */ static void push(int p) {    line[(head + size) % MAXN] = p;    size++;} static int pop(void) {    int p = line[head];    head = (head + 1) % MAXN;    size--;    return p;} /* now까지 도착한 프로세스를 번호 차례로 줄에 세운다 */static void join_until(long long now) {    while (next < n && arrive[next] <= now) push(next++);} int main(void) {    long long q;    scanf("%d %lld", &n, &q);    for (int i = 0; i < n; i++) scanf("%lld %lld", &arrive[i], &left[i]);     long long t = 0; /* 5×10¹²까지 가서 long long */    int done = 0;    while (done < n) {        if (size == 0) { /* 줄이 비면 다음 프로세스가 올 때까지 쉰다 */            if (arrive[next] > t) t = arrive[next];            join_until(t);        }        int p = pop();        long long run = left[p] < q ? left[p] : q;        t += run;        left[p] -= run;        join_until(t); /* 이 시각까지 온 프로세스가 먼저 줄에 서고 */        if (left[p] > 0) {            push(p); /* 그 뒤에 방금 돈 프로세스가 선다 */        } else {            finish[p] = t;            done++;        }    }    for (int i = 0; i < n; i++) printf(i ? " %lld" : "%lld", finish[i]);    putchar('\n');    return 0;}

첫줄 = コンソール.数読み();n = 첫줄[0];q = 첫줄[1];arrive = 新リスト(n, 0);left = 新リスト(n, 0);繰り返す (i = 0; i < n; i++){    줄 = コンソール.数読み();    arrive[i] = 줄[0];    left[i] = 줄[1];} // 원형 큐: 줄에는 많아야 n개라 n칸이면 된다. head는 맨 앞 자리, size는 줄 길이.line = 新リスト(n, 0);head = 0;size = 0;// 아직 줄에 서지 않은 첫 프로세스next = 0; // now까지 도착한 프로세스를 번호 차례로 줄에 세운다줄세우기(now){    間 (next < n && arrive[next] <= now)    {        line[(head + size) % n] = next;        size += 1;        next += 1;    }} finish = 新リスト(n, 0);t = 0;done = 0;間 (done < n){    もし (size == 0)    {        // 줄이 비면 다음 프로세스가 올 때까지 쉰다        t = 数学.大きい方(t, arrive[next]);        줄세우기(t);    }    p = line[head];    head = (head + 1) % n;    size -= 1;    run = 数学.小さい方(q, left[p]);    t += run;    left[p] -= run;    // 이 시각까지 온 프로세스가 먼저 줄에 서고    줄세우기(t);    もし (left[p] > 0)    {        // 그 뒤에 방금 돈 프로세스가 선다        line[(head + size) % n] = p;        size += 1;    }    でなければ    {        finish[p] = t;        done += 1;    }}コンソール.書く(finish);