A sorting network is a device that compares and swaps two positions at a time in a fixed order.
The first line gives the count n, and the second line gives n numbers from left to right.
Call the positions 1, 2, …, n from the left.
The third line gives the number of comparators m, and each of the next m lines gives one comparator as positions i, j (i < j).
Apply the comparators one by one in the given order.
If the number at position i is greater than the number at position j, swap them; otherwise (including when they are equal) leave them.
On the first line print one character per comparator, "x" if it swapped and "." if it left them, m characters with no spaces between.
On the second line print the numbers after all comparators, from left to right, separated by single spaces.
On the third line print "sorted" if those numbers never decrease from left to right (equal neighbours are fine), otherwise "unsorted".
Input
2 ≤ n ≤ 100, numbers are integers from -1,000,000,000 to 1,000,000,000, 1 ≤ m ≤ 1,000, 1 ≤ i < j ≤ n
Output
three lines: the m-character x/. trace, the final numbers, "sorted" or "unsorted"
Example 1 · stdin
4
3 1 3 2
5
1 2
3 4
1 3
2 4
2 3
stdout
xx..x
1 2 3 3
sorted
Example 2 · stdin
3
2 1 0
2
1 2
2 3
stdout
xx
1 0 2
unsorted
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
Swapping two values looks different in each language. Python a[i], a[j] = a[j], a[i], JS/TS [a[i], a[j]] = [a[j], a[i]] (destructuring), C# (a[i], a[j]) = (a[j], a[i]) (tuples), C++ std::swap(a[i], a[j]). Java, C and Craykon have no such one-liner, so use a temporary like t = a[i]; a[i] = a[j]; a[j] = t;. Writing a[i] = a[j]; a[j] = a[i]; without a temporary wipes out the original a[i] on the first line, leaving both slots with the same value. The comparison must be >. With >= equal values are swapped too, so the final numbers look the same but the trace gets extra x's. Printing without a newline: Python print(c, end=""), JS/TS process.stdout.write(c) (console.log always adds a newline), Java System.out.print (unlike println), C# Console.Write (unlike WriteLine), C putchar or printf("%c"), C++ std::cout << c (without std::endl), Craykon Console.Write (Console.WriteLine adds a newline). After the trace, write one newline yourself to end that line so the second line starts separately (Python print(), Craykon Console.WriteLine("")).
Pythonmain.py · 15 lines
n = int(input())a = list(map(int, input().split()))m = int(input())for _ in range(m): i, j = map(int, input().split()) i -= 1 j -= 1 if a[i] > a[j]: a[i], a[j] = a[j], a[i] # 튜플로 한 번에 맞바꾼다 print("x", end="") # end=""라야 줄을 바꾸지 않는다 else: print(".", end="")print() # 표시 줄을 끝낸다print(*a)print("sorted" if all(a[k] <= a[k + 1] for k in range(n - 1)) else "unsorted")
JavaScriptmain.js · 18 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const a = lines[1].trim().split(/\s+/).map(Number);const m = Number(lines[2]);for (let k = 0; k < m; k++) { const [i, j] = lines[3 + k].trim().split(/\s+/).map((v) => Number(v) - 1); if (a[i] > a[j]) { [a[i], a[j]] = [a[j], a[i]]; // 구조 분해로 맞바꾼다 process.stdout.write("x"); // console.log와 달리 줄을 바꾸지 않는다 } else { process.stdout.write("."); }}process.stdout.write("\n");let sorted = true;for (let k = 0; k + 1 < n; k++) if (a[k] > a[k + 1]) sorted = false;console.log(a.join(" "));console.log(sorted ? "sorted" : "unsorted");
TypeScriptmain.ts · 19 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const a: number[] = lines[1].trim().split(/\s+/).map(Number);const m = Number(lines[2]);for (let k = 0; k < m; k++) { const [i, j] = lines[3 + k].trim().split(/\s+/).map((v) => Number(v) - 1); if (a[i] > a[j]) { [a[i], a[j]] = [a[j], a[i]]; // 구조 분해로 맞바꾼다 process.stdout.write("x"); // console.log와 달리 줄을 바꾸지 않는다 } else { process.stdout.write("."); }}process.stdout.write("\n");let sorted = true;for (let k = 0; k + 1 < n; k++) if (a[k] > a[k + 1]) sorted = false;console.log(a.join(" "));console.log(sorted ? "sorted" : "unsorted");
JavaMain.java · 39 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(System.out); int n = Integer.parseInt(in.readLine().trim()); int[] a = new int[n]; StringTokenizer st = new StringTokenizer(in.readLine()); for (int k = 0; k < n; k++) a[k] = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(in.readLine().trim()); for (int k = 0; k < m; k++) { st = new StringTokenizer(in.readLine()); int i = Integer.parseInt(st.nextToken()) - 1, j = Integer.parseInt(st.nextToken()) - 1; if (a[i] > a[j]) { int t = a[i]; // 임시 변수에 하나를 맡겨 두고 맞바꾼다 a[i] = a[j]; a[j] = t; out.print('x'); // print는 줄을 바꾸지 않는다(println은 바꾼다) } else { out.print('.'); } } out.println(); boolean sorted = true; StringBuilder row = new StringBuilder(); for (int k = 0; k < n; k++) { if (k > 0) row.append(' '); row.append(a[k]); if (k + 1 < n && a[k] > a[k + 1]) sorted = false; } out.println(row); out.println(sorted ? "sorted" : "unsorted"); out.flush(); }}
C#Main.cs · 31 lines
using System;using System.Linq;class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int m = int.Parse(Console.ReadLine()); for (int k = 0; k < m; k++) { int[] ij = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int i = ij[0] - 1, j = ij[1] - 1; if (a[i] > a[j]) { (a[i], a[j]) = (a[j], a[i]); // 튜플로 맞바꾼다 Console.Write('x'); // Write는 줄을 바꾸지 않는다(WriteLine은 바꾼다) } else { Console.Write('.'); } } Console.WriteLine(); bool sorted = true; for (int k = 0; k + 1 < n; k++) if (a[k] > a[k + 1]) sorted = false; Console.WriteLine(string.Join(" ", a)); Console.WriteLine(sorted ? "sorted" : "unsorted"); }}
C++main.cpp · 25 lines
#include <algorithm>#include <iostream>#include <utility>#include <vector>int main() { int n, m; std::cin >> n; std::vector<int> a(n); for (int& v : a) std::cin >> v; std::cin >> m; for (int k = 0; k < m; k++) { int i, j; std::cin >> i >> j; if (a[i - 1] > a[j - 1]) { std::swap(a[i - 1], a[j - 1]); // 표준 라이브러리가 맞바꿔 준다 std::cout << 'x'; // endl이나 '\n'을 붙이지 않으면 줄이 이어진다 } else { std::cout << '.'; } } std::cout << '\n'; for (int k = 0; k < n; k++) std::cout << (k ? " " : "") << a[k]; std::cout << '\n' << (std::is_sorted(a.begin(), a.end()) ? "sorted" : "unsorted") << '\n';}
Cmain.c · 32 lines
#include <stdbool.h>#include <stdio.h>int main(void) { int n, m; int a[100]; scanf("%d", &n); for (int k = 0; k < n; k++) scanf("%d", &a[k]); scanf("%d", &m); for (int k = 0; k < m; k++) { int i, j; scanf("%d %d", &i, &j); i--; j--; if (a[i] > a[j]) { int t = a[i]; /* 임시 변수에 하나를 맡겨 두고 맞바꾼다 */ a[i] = a[j]; a[j] = t; putchar('x'); /* 글자 하나만, 줄바꿈 없이 */ } else { putchar('.'); } } putchar('\n'); bool sorted = true; for (int k = 0; k < n; k++) { printf(k ? " %d" : "%d", a[k]); if (k + 1 < n && a[k] > a[k + 1]) sorted = false; } printf("\n%s\n", sorted ? "sorted" : "unsorted"); return 0;}
Craykonmain.cray · 31 lines
n = Console.ReadLine().ToNumber();a = Console.ReadNumbers();m = Console.ReadLine().ToNumber();for (k = 0; k < m; k++){ ij = Console.ReadNumbers(); i = ij[0] - 1; j = ij[1] - 1; if (a[i] > a[j]) { t = a[i]; // 임시 변수에 하나를 맡겨 두고 맞바꾼다 a[i] = a[j]; a[j] = t; Console.Write("x"); // 이어쓰기는 줄을 바꾸지 않는다 } else { Console.Write("."); }}Console.WriteLine(""); // 표시 줄을 끝낸다정렬됨 = true;for (k = 0; k + 1 < n; k++){ if (a[k] > a[k + 1]) { 정렬됨 = false; }}Console.WriteLine(a);Console.WriteLine(정렬됨 ? "sorted" : "unsorted");