A school keeps two ledgers of pairs.
The locker ledger (locker) pairs a locker number (an integer) with a student's name, and the nickname ledger (nick) pairs a nickname with a student's name.
In a pair, the number or nickname is called the left and the name is called the right.
Within one ledger, each left is in at most one pair and each right is in at most one pair.
The two ledgers do not affect each other, and both start empty.
A command has the form "ledger action [values]", where the ledger is locker or nick.
- put a b: remove the pair whose left is a if there is one, remove the pair whose right is b if there is one, and then pair a with b.
- get a: print the right of the pair whose left is a. If there is no such pair, print -.
- find b: print the left of the pair whose right is b. If there is no such pair, print -.
- del a: remove the pair whose left is a, if there is one.
- drop b: remove the pair whose right is b, if there is one.
- size: print the number of pairs in that ledger.
The first line has the number of commands q, and each of the next q lines has one command.
Print one line for every get, find and size.
Write just one generic class (a class template in C++) BiMap<K, V> that takes the left type K and the right type V as parameters, and build both ledgers from it.
Also write a method inverse() that returns a ledger looking at the same pairs the other way round. Its type is BiMap<V, K>.
Input
1 ≤ q ≤ 20000. A locker number is an integer from 0 to 1000000000 written without unnecessary leading zeros. Nicknames and names are 1 to 10 lowercase English letters. Words on a line are separated by single spaces. At least one of get, find, size is given
Output
One line for every get, find and size, in the order the commands appear
Example 1 · stdin
18
locker put 7 ann
locker put 0 bo
nick put ace ann
locker get 7
locker put 7 bo
locker find ann
locker find bo
locker get 0
locker size
locker put 0 cy
locker find cy
locker get 3
locker find dan
locker size
nick find ann
nick drop ann
nick get ace
nick size
stdout
ann
-
7
-
1
0
-
-
2
ace
-
0
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 · 4 languages
This problem accepts only TypeScript, Java, C# and C++, which have generics (a class template in C++). Python and JavaScript do not write types, so one class holds anything from the start (Python's Generic[K, V] is only written down and not checked at run time), and C and Craykon have no type parameters. BiMap<K, V> updates two maps (K→V and V→K) together. inverse() returns a BiMap<V, K> holding the same two maps in swapped places, so find b becomes inverse().get(b) and drop b becomes inverse().remove(b). The point is that there are two type parameters and that they change places. Type arguments are written as BiMap.create<number, string>() in TS, new BiMap<Integer, String>() in Java, new BiMap<int, string>() in C# and BiMap<int, string> in C++. In Java BiMap<int, String> is a compile error (unexpected type), so the numbers are held as Integer. The two ledgers, which differ only in the left type, are handled by one generic function run<K>, which is also given a function that turns a string into K. How to return 'nothing' differs by language. The solutions use V | undefined in TS, null in Java, bool TryGet(K k, out V v) in C# and optional<V> in C++. Trap one: if put does not remove the old pairs, stale pairs stay behind. After locker put 7 bo in the example, locker find ann gives 7, locker get 0 gives bo and locker size gives 2. Trap two: in TS, telling 'nothing' apart with x ? String(x) : "-" treats the number 0 as false too, so locker find cy in the example gives - instead of 0. Ask with x === undefined. Trap three: in C#, if you return default(V) for a missing key and test for null, default is 0 when V is int. locker find ann and locker find dan in the example print 0, which cannot be told apart from the real locker 0. Trap four: in Java, putting the null returned by get into a string with String.valueOf prints null instead of -. Trap five: looking up with operator[] on a C++ map creates the missing key in the map with a default value. A solution that treats the default value as missing makes locker size grow to 2 and 3 in the example, and locker find cy also becomes -. Look up with find.
TypeScriptmain.ts · 68 lines
import { readFileSync } from "node:fs";// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V> { private constructor( private readonly fwd: Map<K, V>, private readonly rev: Map<V, K>, ) {} static create<K, V>(): BiMap<K, V> { return new BiMap<K, V>(new Map<K, V>(), new Map<V, K>()); } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 inverse(): BiMap<V, K> { return new BiMap<V, K>(this.rev, this.fwd); } get(k: K): V | undefined { return this.fwd.get(k); } remove(k: K): void { const v = this.fwd.get(k); if (v === undefined) return; this.fwd.delete(k); this.rev.delete(v); } put(k: K, v: V): void { this.remove(k); this.inverse().remove(v); this.fwd.set(k, v); this.rev.set(v, k); } get size(): number { return this.fwd.size; }}function show<T>(x: T | undefined): string { return x === undefined ? "-" : String(x);}const out: string[] = [];// 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다function run<K>(m: BiMap<K, string>, parse: (s: string) => K, p: string[]): void { const cmd = p[1]; if (cmd === "put") m.put(parse(p[2]), p[3]); else if (cmd === "get") out.push(show(m.get(parse(p[2])))); else if (cmd === "find") out.push(show(m.inverse().get(p[2]))); else if (cmd === "del") m.remove(parse(p[2])); else if (cmd === "drop") m.inverse().remove(p[2]); else out.push(String(m.size));}const lines: string[] = readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const locker = BiMap.create<number, string>();const nick = BiMap.create<string, string>();for (let i = 1; i <= q; i++) { const p = lines[i].trim().split(/\s+/); if (p[0] === "locker") run(locker, Number, p); else run(nick, (s) => s, p);}console.log(out.join("\n"));
JavaMain.java · 67 lines
import java.io.*;import java.util.*;import java.util.function.Function;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V> { private final Map<K, V> fwd; private final Map<V, K> rev; BiMap() { this(new HashMap<>(), new HashMap<>()); } private BiMap(Map<K, V> fwd, Map<V, K> rev) { this.fwd = fwd; this.rev = rev; } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 BiMap<V, K> inverse() { return new BiMap<>(rev, fwd); } // 없으면 null V get(K k) { return fwd.get(k); } void remove(K k) { V v = fwd.remove(k); if (v != null) rev.remove(v); } void put(K k, V v) { remove(k); inverse().remove(v); fwd.put(k, v); rev.put(v, k); } int size() { return fwd.size(); }}public class Main { static StringBuilder sb = new StringBuilder(); static <T> String show(T x) { return x == null ? "-" : x.toString(); } // 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다 static <K> void run(BiMap<K, String> m, Function<String, K> parse, String[] p) { switch (p[1]) { case "put": m.put(parse.apply(p[2]), p[3]); break; case "get": sb.append(show(m.get(parse.apply(p[2])))).append('\n'); break; case "find": sb.append(show(m.inverse().get(p[2]))).append('\n'); break; case "del": m.remove(parse.apply(p[2])); break; case "drop": m.inverse().remove(p[2]); break; default: sb.append(m.size()).append('\n'); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); BiMap<Integer, String> locker = new BiMap<>(); // int는 타입 인자가 될 수 없어 Integer로 담는다 BiMap<String, String> nick = new BiMap<>(); for (int i = 0; i < q; i++) { String[] p = br.readLine().trim().split(" "); if (p[0].equals("locker")) run(locker, Integer::valueOf, p); else run(nick, s -> s, p); } System.out.print(sb); }}
C#Main.cs · 79 lines
using System;using System.Collections.Generic;using System.Text;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V>{ private readonly Dictionary<K, V> fwd; private readonly Dictionary<V, K> rev; public BiMap() : this(new Dictionary<K, V>(), new Dictionary<V, K>()) { } private BiMap(Dictionary<K, V> fwd, Dictionary<V, K> rev) { this.fwd = fwd; this.rev = rev; } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 public BiMap<V, K> Inverse() => new BiMap<V, K>(rev, fwd); // 있는지 없는지를 bool로 돌려주고, 값은 out으로 내보낸다 public bool TryGet(K k, out V v) => fwd.TryGetValue(k, out v); public void Remove(K k) { if (fwd.Remove(k, out V v)) rev.Remove(v); } public void Put(K k, V v) { Remove(k); Inverse().Remove(v); fwd[k] = v; rev[v] = k; } public int Count => fwd.Count;}class Program{ static readonly StringBuilder sb = new StringBuilder(); // 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다 static void Run<K>(BiMap<K, string> m, Func<string, K> parse, string[] p) { switch (p[1]) { case "put": m.Put(parse(p[2]), p[3]); break; case "get": if (m.TryGet(parse(p[2]), out string name)) sb.Append(name); else sb.Append('-'); sb.Append('\n'); break; case "find": if (m.Inverse().TryGet(p[2], out K left)) sb.Append(left); else sb.Append('-'); sb.Append('\n'); break; case "del": m.Remove(parse(p[2])); break; case "drop": m.Inverse().Remove(p[2]); break; default: sb.Append(m.Count).Append('\n'); break; } } static void Main() { var lines = Console.In.ReadToEnd().Split('\n'); int q = int.Parse(lines[0].Trim()); var locker = new BiMap<int, string>(); // int를 포장 없이 그대로 담는다 var nick = new BiMap<string, string>(); for (int i = 1; i <= q; i++) { var p = lines[i].Trim().Split(' '); if (p[0] == "locker") Run(locker, int.Parse, p); else Run(nick, s => s, p); } Console.Write(sb); }}
C++main.cpp · 89 lines
#include <iostream>#include <map>#include <memory>#include <optional>#include <string>using namespace std;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전template <class K, class V>class BiMap { shared_ptr<map<K, V>> fwd_; shared_ptr<map<V, K>> rev_;public: BiMap() : fwd_(make_shared<map<K, V>>()), rev_(make_shared<map<V, K>>()) {} BiMap(shared_ptr<map<K, V>> fwd, shared_ptr<map<V, K>> rev) : fwd_(std::move(fwd)), rev_(std::move(rev)) {} // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 BiMap<V, K> inverse() const { return BiMap<V, K>(rev_, fwd_); } // find는 없는 키를 만들지 않는다 optional<V> get(const K& k) const { auto it = fwd_->find(k); if (it == fwd_->end()) return nullopt; return it->second; } void remove(const K& k) { auto it = fwd_->find(k); if (it == fwd_->end()) return; rev_->erase(it->second); fwd_->erase(it); } void put(const K& k, const V& v) { remove(k); inverse().remove(v); (*fwd_)[k] = v; (*rev_)[v] = k; } size_t size() const { return fwd_->size(); }};template <class T>void show(const optional<T>& x) { if (x) cout << *x << '\n'; else cout << "-\n";}// 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다template <class K, class Parse>void run(BiMap<K, string>& m, Parse parse, const string& cmd) { string a, b; if (cmd == "put") { cin >> a >> b; m.put(parse(a), b); } else if (cmd == "get") { cin >> a; show(m.get(parse(a))); } else if (cmd == "find") { cin >> b; show(m.inverse().get(b)); } else if (cmd == "del") { cin >> a; m.remove(parse(a)); } else if (cmd == "drop") { cin >> b; m.inverse().remove(b); } else { cout << m.size() << '\n'; }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; BiMap<int, string> locker; BiMap<string, string> nick; for (int i = 0; i < q; i++) { string ledger, cmd; cin >> ledger >> cmd; if (ledger == "locker") run(locker, [](const string& s) { return stoi(s); }, cmd); else run(nick, [](const string& s) { return s; }, cmd); } return 0;}