On a warehouse belt there were n boxes with number tags in one row.
A robot did q jobs in order, and now only the job log and the row after all the jobs are left.
Positions count the first box as 1 in the row at the time of that job.
S i j swapped the i-th box and the j-th box.
M i j took out the i-th box (the boxes behind it move one place forward) and put it back so that it became the j-th box of the new row.
L k took the first box and put it at the very end, k times.
F i j reversed the boxes from the i-th to the j-th in place.
The first line gives n and q.
The second line gives the row after all the jobs, as n tags starting from the first box.
Each of the next q lines gives one job, in the order the robot did them.
The last line gives an integer t.
Values on one line are separated by single spaces.
On the first line print the row just before the t-th job, and on the second line the original row before the first job.
A row is written as its tags from the first box, separated by single spaces.
Go through the log backward, from the last job to the first, and undo each job.
Input
1 ≤ n ≤ 1,000. 1 ≤ q ≤ 2,000. Tags are integers from 1 to 1,000,000 (plain digits without commas) and the same tag may appear more than once. For S and M, 1 ≤ i ≤ n and 1 ≤ j ≤ n (i and j may be equal). For F, 1 ≤ i ≤ j ≤ n. For L, 1 ≤ k ≤ n. 1 ≤ t ≤ q
Output
Two lines: the row just before the t-th job, then the original row (n tags each)
Example 1 · stdin
5 4
30 20 50 10 40
M 1 4
L 2
S 1 5
F 2 4
3
stdout
40 10 50 20 30
10 20 30 40 50
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 backward loop looks different in each language. In Python it is for idx in range(q - 1, -1, -1); the end value is not included, so to reach index 0 you write -1 as the end. range(q - 1, 0, -1) misses the first job. JS, TS, Java, C#, C and C++ write for (int idx = q - 1; idx >= 0; idx--) and Craykon for (idx = q - 1; idx >= 0; idx--). Starting at q with the condition idx > 0 reads slot q, which does not exist, and misses slot 0. In C and C++, if the index is unsigned or size_t, 0 minus 1 becomes a huge number, so idx >= 0 is always true, the loop never ends and it reads outside the array. C++ ops.at(idx) then throws an exception and stops, but for ops[idx] or a C array what happens is undefined. You can also reverse the list and loop forward. Python reversed(ops) gives a reversed view to loop over, but ops.reverse() reverses in place and returns None, so for op in ops.reverse() is a TypeError. JS ops.reverse() reverses in place and returns that same array. C++ can loop from rbegin() to rend(). Reversing the order is not enough: each job must also be undone by its opposite. In the example, undoing the log from the front gives the wrong first row 20 30 10 40 50. S and F undo themselves when done again, but M i j must take the box out of position j and put it at position i (Python row.insert(i - 1, row.pop(j - 1)), Craykon RemoveAt and Insert), and L k must bring the last k boxes to the front (Python row[n - k:] + row[:n - k], Java Collections.rotate(row, k), C++ std::rotate). Finally, 'just before the t-th job' is right after undoing the t-th job. Counting from 0 that job is number t - 1, so print when idx == t - 1. Printing when idx == t gives the row after the t-th job, and when t is q that line never appears at all.
Pythonmain.py · 28 lines
import syslines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())row = lines[1].split()ops = [lines[2 + i].split() for i in range(q)]t = int(lines[2 + q])out = []# 마지막 작업부터 첫 작업까지 거꾸로: range의 끝 -1은 들어가지 않으므로 0번까지 돈다for idx in range(q - 1, -1, -1): op = ops[idx] a = int(op[1]) if op[0] == "S": # 맞바꾸기는 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1], row[b - 1] = row[b - 1], row[a - 1] elif op[0] == "M": # i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = int(op[2]) row.insert(a - 1, row.pop(b - 1)) elif op[0] == "L": # 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row[n - a:] + row[:n - a] else: # F: 뒤집기도 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1:b] = row[a - 1:b][::-1] if idx == t - 1: # t번 작업을 되돌린 직후 = t번 작업을 하기 직전 out.append(" ".join(row))out.append(" ".join(row))print("\n".join(out))
JavaScriptmain.js · 29 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row = lines[1].trim().split(/\s+/);const ops = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t = Number(lines[2 + q]);const out = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 31 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row: string[] = lines[1].trim().split(/\s+/);const ops: string[][] = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t: number = Number(lines[2 + q]);const out: string[] = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
JavaMain.java · 42 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] head = in.readLine().trim().split("\\s+"); int n = Integer.parseInt(head[0]), q = Integer.parseInt(head[1]); List<String> row = new ArrayList<>(Arrays.asList(in.readLine().trim().split("\\s+"))); String[][] ops = new String[q][]; for (int i = 0; i < q; i++) ops[i] = in.readLine().trim().split("\\s+"); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { String[] op = ops[idx]; int a = Integer.parseInt(op[1]); switch (op[0]) { case "S": Collections.swap(row, a - 1, Integer.parseInt(op[2]) - 1); break; case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 row.add(a - 1, row.remove(Integer.parseInt(op[2]) - 1)); break; case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 Collections.rotate(row, a); break; default: Collections.reverse(row.subList(a - 1, Integer.parseInt(op[2]))); } if (idx == t - 1) out.append(String.join(" ", row)).append('\n'); // t번 작업을 하기 직전 } out.append(String.join(" ", row)).append('\n'); System.out.print(out); }}
C#Main.cs · 57 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(head[0]), q = int.Parse(head[1]); var row = new List<string>(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)); var ops = new string[q][]; for (int i = 0; i < q; i++) ops[i] = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int t = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { string[] op = ops[idx]; int a = int.Parse(op[1]); switch (op[0]) { case "S": { int b = int.Parse(op[2]); (row[a - 1], row[b - 1]) = (row[b - 1], row[a - 1]); break; } case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 { int b = int.Parse(op[2]); string box = row[b - 1]; row.RemoveAt(b - 1); row.Insert(a - 1, box); break; } case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 { List<string> tail = row.GetRange(n - a, a); row.RemoveRange(n - a, a); row.InsertRange(0, tail); break; } default: { int b = int.Parse(op[2]); row.Reverse(a - 1, b - a + 1); // (시작 자리, 개수) break; } } if (idx == t - 1) sb.Append(string.Join(" ", row)).Append('\n'); // t번 작업을 하기 직전 } sb.Append(string.Join(" ", row)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 49 lines
#include <algorithm>#include <iostream>#include <vector>struct Op { char kind; int a, b;};static void printRow(const std::vector<int>& row) { for (size_t i = 0; i < row.size(); i++) std::cout << (i ? " " : "") << row[i]; std::cout << '\n';}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q, t; std::cin >> n >> q; std::vector<int> row(n); for (int& x : row) std::cin >> x; std::vector<Op> ops(q); for (Op& op : ops) { std::cin >> op.kind >> op.a; op.b = 0; if (op.kind != 'L') std::cin >> op.b; } std::cin >> t; // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { const Op& op = ops[idx]; if (op.kind == 'S') { std::swap(row[op.a - 1], row[op.b - 1]); } else if (op.kind == 'M') { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 int box = row[op.b - 1]; row.erase(row.begin() + (op.b - 1)); row.insert(row.begin() + (op.a - 1), box); } else if (op.kind == 'L') { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 std::rotate(row.begin(), row.end() - op.a, row.end()); } else { std::reverse(row.begin() + (op.a - 1), row.begin() + op.b); } if (idx == t - 1) printRow(row); // t번 작업을 하기 직전 } printRow(row);}
Cmain.c · 56 lines
#include <stdio.h>#include <string.h>#define MAXN 1000#define MAXQ 2000static int row[MAXN], tmp[MAXN];static char kind[MAXQ];static int pa[MAXQ], pb[MAXQ];static void print_row(int n) { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", row[i]); putchar('\n');}int main(void) { int n, q, t; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d", &row[i]); for (int i = 0; i < q; i++) { scanf(" %c %d", &kind[i], &pa[i]); pb[i] = 0; if (kind[i] != 'L') scanf("%d", &pb[i]); } scanf("%d", &t); /* 마지막 작업부터 첫 작업까지 거꾸로 */ for (int idx = q - 1; idx >= 0; idx--) { int a = pa[idx], b = pb[idx]; if (kind[idx] == 'S') { int x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; } else if (kind[idx] == 'M') { /* i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 */ int box = row[b - 1]; if (b < a) memmove(&row[b - 1], &row[b], (size_t)(a - b) * sizeof(int)); else memmove(&row[a], &row[a - 1], (size_t)(b - a) * sizeof(int)); row[a - 1] = box; } else if (kind[idx] == 'L') { /* 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 */ memcpy(tmp, &row[n - a], (size_t)a * sizeof(int)); memcpy(tmp + a, row, (size_t)(n - a) * sizeof(int)); memcpy(row, tmp, (size_t)n * sizeof(int)); } else { for (int l = a - 1, r = b - 1; l < r; l++, r--) { int x = row[l]; row[l] = row[r]; row[r] = x; } } if (idx == t - 1) print_row(n); /* t번 작업을 하기 직전 */ } print_row(n); return 0;}
Craykonmain.cray · 60 lines
head = Console.ReadNumbers();n = head[0];q = head[1];row = Console.ReadNumbers();ops = [];for (i = 0; i < q; i++){ ops.Add(Console.ReadLine().Trim().Split(" "));}t = Console.ReadLine().ToNumber();// 마지막 작업부터 첫 작업까지 거꾸로for (idx = q - 1; idx >= 0; idx--){ op = ops[idx]; a = op[1].ToNumber(); switch (op[0]) { case "S": b = op[2].ToNumber(); x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; break; case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = op[2].ToNumber(); box = row[b - 1]; row.RemoveAt(b - 1); row.Insert(a - 1, box); break; case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 앞 = row.GetRange(0, n - a); row = row.GetRange(n - a, a); foreach (v in 앞) { row.Add(v); } break; default: l = a - 1; r = op[2].ToNumber() - 1; while (l < r) { x = row[l]; row[l] = row[r]; row[r] = x; l++; r--; } break; } if (idx == t - 1) { // t번 작업을 하기 직전 Console.WriteLine(row.Join(" ")); }}Console.WriteLine(row.Join(" "));