A concert hall has two entrances, A and B.
Each entrance logs the entry time (in seconds) of its visitors in the order they came in. So each log is in order from the earliest time (several visitors may share a time).
Merge the two logs into one list in order of entry time.
When times are equal, a visitor from entrance A comes before a visitor from entrance B. Visitors from the same entrance keep their order in the original log.
The front of the list is number 1.
On the first line, print the list numbers of the entrance A visitors in the order of log A, separated by single spaces.
On the second line, print the list numbers of the entrance B visitors in the order of log B, the same way.
The first input line gives the sizes n of log A and m of log B, the second line gives the n times of A, and the third line gives the m times of B.
Input
1 ≤ n, m ≤ 10,000, 0 ≤ time ≤ 1,000,000,000 (integers). The times on each line never decrease
Output
Two lines: the list numbers of the A visitors, then of the B visitors
Example 1 · stdin
4 3
5 9 9 120
3 9 40
stdout
2 3 4 7
1 5 6
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
Both logs are already sorted, so keep one finger in each log (positions i and j), put the earlier visitor on the list and move only that finger; it ends after n + m steps. Equal times go to A first, so the condition for taking A is a[i] <= b[j]. Writing < lets B in first on equal times. When one log runs out, the rest of the other log must all go at the end. Looping only while (i < n && j < m) and stopping drops that tail, so write the condition as j == m || (i < n && a[i] <= b[j]) and finish everything in one loop. Ask i < n first so you never read past a finished log (&& skips the right side when the left is false; written the other way round, a[i] <= b[j] && i < n, Python, Java, C# and Craykon stop with an out-of-range error). Collecting everything and sorting also works, but JS/TS sort() without a compare function turns the values into strings and orders them alphabetically, so 100 comes before 9. In Java, comparing two values of a List<Integer> with == checks whether they are the same object, so equal times outside -128 to 127 compare as different. Store them in an int[], or use equals or intValue(). To print numbers on one line separated by spaces, Python print(*pos), JS/TS/C# join(" ") and Craykon Console.WriteLine(list) put spaces only between values; in C, C++ and Java take care yourself not to put a space before the first number.
Pythonmain.py · 18 lines
n, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))pos_a, pos_b = [], []i = j = 0place = 1while i < n or j < m: # A를 고르는 때: B가 다 끝났거나, A의 시각이 B보다 이르거나 같을 때(같으면 A가 먼저) if j == m or (i < n and a[i] <= b[j]): pos_a.append(place) i += 1 else: pos_b.append(place) j += 1 place += 1print(*pos_a)print(*pos_b)
JavaScriptmain.js · 17 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a = lines[1].trim().split(/\s+/).map(Number);const b = lines[2].trim().split(/\s+/).map(Number);const posA = [], posB = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) { // B가 끝났거나 A가 이르거나 같으면 A가 먼저 if (j === m || (i < n && a[i] <= b[j])) { posA.push(place); i++; } else { posB.push(place); j++; }}console.log(posA.join(" ") + "\n" + posB.join(" "));
TypeScriptmain.ts · 17 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a: number[] = lines[1].trim().split(/\s+/).map(Number);const b: number[] = lines[2].trim().split(/\s+/).map(Number);const posA: number[] = [], posB: number[] = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) { if (j === m || (i < n && a[i] <= b[j])) { posA.push(place); i++; } else { posB.push(place); j++; }}console.log(posA.join(" ") + "\n" + posB.join(" "));
JavaMain.java · 33 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int[] readInts(BufferedReader br, int k) throws Exception { StringTokenizer st = new StringTokenizer(br.readLine()); int[] r = new int[k]; for (int t = 0; t < k; t++) r[t] = Integer.parseInt(st.nextToken()); return r; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()); int[] a = readInts(br, n), b = readInts(br, m); // int[]라 ==가 값을 비교한다 StringBuilder outA = new StringBuilder(), outB = new StringBuilder(); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { if (outA.length() > 0) outA.append(' '); outA.append(place); i++; } else { if (outB.length() > 0) outB.append(' '); outB.append(place); j++; } } System.out.print(outA + "\n" + outB + "\n"); }}
C#Main.cs · 31 lines
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]), m = int.Parse(first[1]); int[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); int[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); var posA = new List<int>(n); var posB = new List<int>(m); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { posA.Add(place); i++; } else { posB.Add(place); j++; } } Console.WriteLine(string.Join(" ", posA)); Console.WriteLine(string.Join(" ", posB)); }}
C++main.cpp · 30 lines
#include <iostream>#include <vector>void printLine(const std::vector<int>& p) { for (size_t t = 0; t < p.size(); t++) std::cout << (t ? " " : "") << p[t]; std::cout << "\n";}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> a(n), b(m); for (int& x : a) std::cin >> x; for (int& x : b) std::cin >> x; std::vector<int> posA, posB; int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { posA.push_back(place); i++; } else { posB.push_back(place); j++; } } printLine(posA); printLine(posB);}
Cmain.c · 28 lines
#include <stdio.h>static int a[10000], b[10000];static int pos_a[10000], pos_b[10000];static void print_line(const int *p, int k) { for (int t = 0; t < k; t++) printf(t ? " %d" : "%d", p[t]); printf("\n");}int main(void) { int n, m; scanf("%d %d", &n, &m); for (int t = 0; t < n; t++) scanf("%d", &a[t]); for (int t = 0; t < m; t++) scanf("%d", &b[t]); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { /* B가 끝났거나 A가 이르거나 같으면 A가 먼저 */ if (j == m || (i < n && a[i] <= b[j])) { pos_a[i++] = place; } else { pos_b[j++] = place; } } print_line(pos_a, n); print_line(pos_b, m); return 0;}
Craykonmain.cray · 27 lines
first = Console.ReadNumbers();n = first[0];m = first[1];a = Console.ReadNumbers();b = Console.ReadNumbers();posA = [];posB = [];i = 0;j = 0;for (place = 1; place <= n + m; place++){ // B가 끝났거나, A가 남아 있고 A의 시각이 이르거나 같으면 A가 먼저 // &&는 앞이 거짓이면 뒤를 보지 않으니 i < n을 먼저 묻는다 takeA = j == m || i < n && a[i] <= b[j]; if (takeA) { posA.Add(place); i++; } else { posB.Add(place); j++; }}Console.WriteLine(posA);Console.WriteLine(posB);