swapping elementssorting listsslicing listsP0177

Tidying ranges of a warehouse shelf

A warehouse shelf holds n boxes in one row, in slots numbered 1, 2, …, n from the left. The second line gives the n box weights in slot order. The third line gives the number of commands q, and each of the next q lines gives one command. There are three kinds of command. "swap i j" trades the boxes in slot i and slot j (if i equals j nothing changes, and i may be larger than j). "sort l r" rearranges only the boxes in slots l through r (both ends included) so that lighter boxes are on the left. Boxes outside that range do not move. "show l r" prints the current weights in slots l through r (both ends included) on one line, separated by single spaces. Print one line for each show command, in command order.

Input: 1 ≤ n ≤ 1000, 1 ≤ q ≤ 1000, 1 ≤ weight ≤ 1,000,000 (integers).
For swap 1 ≤ i, j ≤ n; for sort and show 1 ≤ l ≤ r ≤ n.
There is at least one show command, and all show commands together print at most 20,000 weights
Output: One line per show command

Example 1 · stdin

6
30 4 100 25 9 7
5
sort 2 5
show 1 6
swap 1 6
sort 4 6
show 3 5

stdout

30 4 9 25 100 7
9 25 30

Example 2 · stdin

3
5 1 3
4
show 2 2
swap 3 3
sort 1 1
show 1 3

stdout

1
5 1 3

main.py Programming language Runtime version

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

Cutting out and sorting one range of a list splits the languages on two questions: is the end included, and is it a copy or in place?
Cutting 1-based l to r (both ends included): Python a[l-1:r], JS/TS a.slice(l-1, r), Java Arrays.copyOfRange(a, l-1, r) (all three leave the end index out), the C# range a[(l-1)..r] (also leaves the end out), Craykon a.GetRange(l-1, r-l+1) (Korean 부분목록, start and count).
Sorting a range: Java Arrays.sort(a, l-1, r) and C++ std::sort(a.begin()+l-1, a.begin()+r) leave the end out and sort in place, while C# Array.Sort(a, l-1, r-l+1) and C qsort(a+l-1, r-l+1, …) take a start and a count.
Trap one: Python a[l-1:r].sort() sorts a copy of the slice and throws it away, so the shelf does not change.
Put it back with a[l-1:r] = sorted(a[l-1:r]).
A Craykon GetRange is also a new list, so you write it back cell by cell after sorting, and JS puts it back with splice.
Trap two: JS/TS sort() without a compare function compares numbers as strings, turning [10, 9, 100] into [10, 100, 9].
Use sort((u, v) => u - v).
Trap three: passing the end index as the third argument, as in C# Array.Sort(a, start, end), gives the wrong count, so it sorts past the range or throws.
Trap four: cutting one short, as in a[l-1:r-1], drops slot r.
Swapping two cells: Python a[i], a[j] = a[j], a[i], JS/TS destructuring, a C# tuple, C++ std::swap, and a temporary variable in Java, C and Craykon.

Pythonmain.py · 18 lines

import sys lines = sys.stdin.read().split("\n")n = int(lines[0])shelf = list(map(int, lines[1].split()))q = int(lines[2])out = []for line in lines[3:3 + q]:    cmd, a, b = line.split()    a, b = int(a) - 1, int(b)          # 0부터 세는 시작 a, 끝 b(b는 들어가지 않음)    if cmd == "swap":        i, j = a, b - 1        shelf[i], shelf[j] = shelf[j], shelf[i]    elif cmd == "sort":        shelf[a:b] = sorted(shelf[a:b])  # 잘라 낸 것은 사본이라 정렬한 뒤 그 자리에 다시 넣는다    else:        out.append(" ".join(map(str, shelf[a:b])))print("\n".join(out))

JavaScriptmain.js · 19 lines

const lines = require("fs").readFileSync(0, "utf8").split("\n");const shelf = lines[1].trim().split(/\s+/).map(Number);const q = Number(lines[2]);const out = [];for (const line of lines.slice(3, 3 + q)) {  const [cmd, x, y] = line.trim().split(" ");  const a = Number(x) - 1;  const b = Number(y); // slice(a, b)는 b를 넣지 않는다  if (cmd === "swap") {    [shelf[a], shelf[b - 1]] = [shelf[b - 1], shelf[a]];  } else if (cmd === "sort") {    // 비교 함수가 없으면 문자열로 비교해서 "10" < "9"가 된다    const part = shelf.slice(a, b).sort((u, v) => u - v);    shelf.splice(a, part.length, ...part);  } else {    out.push(shelf.slice(a, b).join(" "));  }}console.log(out.join("\n"));

TypeScriptmain.ts · 20 lines

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const shelf: number[] = lines[1].trim().split(/\s+/).map(Number);const q = Number(lines[2]);const out: string[] = [];for (const line of lines.slice(3, 3 + q)) {  const [cmd, x, y] = line.trim().split(" ");  const a = Number(x) - 1;  const b = Number(y); // slice(a, b)는 b를 넣지 않는다  if (cmd === "swap") {    [shelf[a], shelf[b - 1]] = [shelf[b - 1], shelf[a]];  } else if (cmd === "sort") {    // 비교 함수가 없으면 문자열로 비교해서 "10" < "9"가 된다    const part: number[] = shelf.slice(a, b).sort((u, v) => u - v);    shelf.splice(a, part.length, ...part);  } else {    out.push(shelf.slice(a, b).join(" "));  }}console.log(out.join("\n"));

JavaMain.java · 29 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));        int n = Integer.parseInt(br.readLine().trim());        int[] shelf = Arrays.stream(br.readLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();        int q = Integer.parseInt(br.readLine().trim());        StringBuilder out = new StringBuilder();        for (int k = 0; k < q; k++) {            String[] p = br.readLine().trim().split(" ");            int a = Integer.parseInt(p[1]) - 1;            int b = Integer.parseInt(p[2]); // 끝 자리 b는 들어가지 않는다(toIndex)            if (p[0].equals("swap")) {                int tmp = shelf[a];                shelf[a] = shelf[b - 1];                shelf[b - 1] = tmp;            } else if (p[0].equals("sort")) {                Arrays.sort(shelf, a, b); // 그 구간만 제자리에서 정렬            } else {                StringJoiner sj = new StringJoiner(" ");                for (int w : Arrays.copyOfRange(shelf, a, b)) sj.add(String.valueOf(w));                out.append(sj).append('\n');            }        }        System.out.print(out);    }}

C#Main.cs · 32 lines

using System;using System.Linq;using System.Text; class Program{    static void Main()    {        Console.ReadLine();        int[] shelf = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();        int q = int.Parse(Console.ReadLine().Trim());        var sb = new StringBuilder();        for (int k = 0; k < q; k++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int a = int.Parse(p[1]) - 1, b = int.Parse(p[2]) - 1; // 둘 다 0부터, b도 들어간다            if (p[0] == "swap")            {                (shelf[a], shelf[b]) = (shelf[b], shelf[a]);            }            else if (p[0] == "sort")            {                Array.Sort(shelf, a, b - a + 1); // (시작, 개수)다. 끝 자리가 아니다            }            else            {                sb.Append(string.Join(" ", shelf[a..(b + 1)])).Append('\n'); // 범위 a..c 는 c를 넣지 않는다            }        }        Console.Write(sb);    }}

C++main.cpp · 29 lines

#include <algorithm>#include <iostream>#include <string>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    int n, q;    std::cin >> n;    std::vector<int> shelf(n);    for (int& w : shelf) std::cin >> w;    std::cin >> q;    std::string out;    for (int k = 0; k < q; k++) {        std::string cmd;        int a, b;        std::cin >> cmd >> a >> b;        if (cmd == "swap") {            std::swap(shelf[a - 1], shelf[b - 1]);        } else if (cmd == "sort") {            std::sort(shelf.begin() + (a - 1), shelf.begin() + b); // [첫, 끝) — 끝은 들어가지 않는다        } else {            for (int i = a - 1; i < b; i++) out += (i > a - 1 ? " " : "") + std::to_string(shelf[i]);            out += "\n";        }    }    std::cout << out;}

Cmain.c · 32 lines

#include <stdio.h>#include <stdlib.h> static int ascending(const void* x, const void* y) {    int a = *(const int*)x, b = *(const int*)y;    return (a > b) - (a < b);} int main(void) {    static int shelf[1000];    int n, q;    scanf("%d", &n);    for (int i = 0; i < n; i++) scanf("%d", &shelf[i]);    scanf("%d", &q);    for (int k = 0; k < q; k++) {        char cmd[8];        int a, b;        scanf("%7s %d %d", cmd, &a, &b);        a--, b--; /* 둘 다 0부터 */        if (cmd[1] == 'w') { /* swap */            int tmp = shelf[a];            shelf[a] = shelf[b];            shelf[b] = tmp;        } else if (cmd[1] == 'o') { /* sort: a번부터 (b - a + 1)칸 */            qsort(shelf + a, b - a + 1, sizeof shelf[0], ascending);        } else { /* show */            for (int i = a; i <= b; i++) printf(i > a ? " %d" : "%d", shelf[i]);            printf("\n");        }    }    return 0;}

Craykonmain.cray · 29 lines

n = Console.ReadLine().ToNumber();shelf = Console.ReadNumbers();q = Console.ReadLine().ToNumber();for (k = 0; k < q; k++){    p = Console.ReadLine().Trim().Split();    a = p[1].ToNumber() - 1;    b = p[2].ToNumber() - 1; // 둘 다 0부터, b도 들어간다    if (p[0] == "swap")    {        tmp = shelf[a];        shelf[a] = shelf[b];        shelf[b] = tmp;    }    else if (p[0] == "sort")    {        // 부분목록은 (시작, 개수)로 잘라 낸 새 목록이라, 정렬한 뒤 제자리에 다시 써 넣는다        part = shelf.GetRange(a, b - a + 1);        part.Sort();        for (i = 0; i < part.Count; i++)        {            shelf[a + i] = part[i];        }    }    else    {        Console.WriteLine(shelf.GetRange(a, b - a + 1).Join(" "));    }}