Wires are laid on a grid board that is endlessly wide.
A cell is named by integer coordinates (x, y), and at first every cell is empty.
The first line has the number of commands q, and the next q lines have the commands, one per line.
"lay x y path" lays one wire that starts at cell (x, y) and moves one cell at a time, following the letters of path from the front.
The letter U moves to the cell where y is 1 larger, D to the cell where y is 1 smaller, L to the cell where x is 1 smaller, and R to the cell where x is 1 larger.
The wire occupies the start cell and every cell it moves onto.
A wire may pass again over a cell it has already passed, and such a cell is counted once.
If at least one of the cells it passes is occupied by another wire, this wire cannot be laid.
In that case print "blocked id", where id is the number of the wire in the first occupied cell met when going from the start cell in path order.
A wire that cannot be laid leaves no cell on the board.
If it is not blocked, the wire is laid, and you print the number of cells it occupies as "ok cells".
Laid wires get the numbers 1, 2, 3, … in the order they are laid, and a wire that cannot be laid gets no number.
"cut x y" removes the whole wire that occupies cell (x, y).
If there is such a wire, every cell it occupies becomes empty and you print "removed id"; if there is none, print "none".
The number of a removed wire is never used again.
After all commands, print on the last line the number of wires left on the board and the number of occupied cells, separated by a single space.
Input
1 ≤ q ≤ 2,000. x and y in a command are integers between −1,000,000,000 and 1,000,000,000, and a negative one starts with -. path is 1 to 100 letters from U, D, L, R. At any moment at most 9,000 cells are occupied
Output
One line per command (ok cells, blocked id, removed id, none), then a last line with the number of wires left and the number of occupied cells
ok 4
blocked 1
ok 4
removed 1
none
ok 3
none
ok 2
ok 2
4 11
Example 2 · stdin
5
lay 1000000000 1000000000 L
lay 1000000000 999999999 L
lay 999999997 999999999 RRUL
cut 999999999 999999999
cut -1000000000 -1000000000
stdout
ok 2
ok 2
blocked 2
removed 2
none
1 2
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
This problem asks 'who occupies this cell' by whether a key exists in a map from cell → wire number. The coordinates go to ±1 billion, so a 2D array is impossible. The languages split on the key being two coordinates. Python uses the tuple (x, y) itself as the key and asks (x, y) in owner. C# uses a value tuple, Dictionary<(int, int), int>, with ContainsKey or TryGetValue, and C++ uses std::map<std::pair<int, int>, int> with find (std::unordered_map has no hash for a pair, so it does not compile as it is). A JS/TS Map accepts an array as a key, but it only checks whether it is the same array, not the same contents. Java uses HashMap<Long, Integer> with both coordinates packed into one long and containsKey or get, and Craykon uses Dict() with the string "" + x + "," + y as the key and asks owner.Contains(key). C has no map, so it builds a hash table by hand and leaves a mark in a deleted slot so that cells after it can still be found. Trap one: JS map.has([1, 2]) is always false, because it is a different array from the [1, 2] just stored. The second command of the first example is not blocked. Use a string such as x + "," + y as the key. Trap two: when making a string, without a separator both (1, 23) and (12, 3) become "123" (last two commands of the first example). Trap three: when packing into one number, JS x * 4000000000 + y reaches 4 × 10^18, which is past 2^53, and neighbouring cells become the same number (second command of the second example). Java ((long) x << 32) | y sets all upper 32 bits to 1 when y is negative, so x disappears and (0, −1) and (1, −1) are the same key (cut 0 -1 in the first example). Keep only the lower 32 bits with y & 0xFFFFFFFFL. Trap four: a blocked wire lays no cell. If you check while laying cell by cell, the cells laid before the block stay, and the sixth command of the first example is blocked by such a cell. Check the whole path first, then lay. Trap five: a cell the wire passes again is not a block and is counted once. RULDR is 4 cells, not 6. Trap six: cutting must delete the key: Python del owner[cell], JS/TS delete(key), Java remove, C# Remove, C++ erase, Craykon Remove. If you only change the value to 0, 'does the key exist' is still true and an empty cell looks occupied. Trap seven: the number after blocked is the wire in the first cell met in path order, not the smallest number among the blocking wires (third command of the second example).
Pythonmain.py · 44 lines
import sysSTEP = {"U": (0, 1), "D": (0, -1), "L": (-1, 0), "R": (1, 0)}def main(): lines = sys.stdin.read().split("\n") q = int(lines[0]) owner = {} # (x, y) → 전선 번호. 튜플은 값이 같으면 같은 열쇠다 wires = {} # 전선 번호 → 그 전선이 차지한 칸들 next_id = 1 out = [] for line in lines[1:1 + q]: parts = line.split() x, y = int(parts[1]), int(parts[2]) if parts[0] == "lay": path = [(x, y)] for ch in parts[3]: dx, dy = STEP[ch] x, y = x + dx, y + dy path.append((x, y)) hit = next((cell for cell in path if cell in owner), None) # 길 순서로 처음 막히는 칸 if hit is not None: out.append(f"blocked {owner[hit]}") # 아무 칸도 놓지 않는다 continue mine = list(dict.fromkeys(path)) # 자기 길을 다시 지나는 칸은 한 번만 for cell in mine: owner[cell] = next_id wires[next_id] = mine out.append(f"ok {len(mine)}") next_id += 1 else: if (x, y) in owner: wire = owner[(x, y)] for cell in wires.pop(wire): del owner[cell] # 값을 0으로 바꾸는 것이 아니라 열쇠를 지운다 out.append(f"removed {wire}") else: out.append("none") out.append(f"{len(wires)} {len(owner)}") print("\n".join(out))main()
JavaScriptmain.js · 43 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const STEP = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };const q = Number(lines[0]);const owner = new Map(); // "x,y" → 전선 번호. 배열 [x, y]는 내용이 같아도 다른 열쇠라서 문자열로 만든다const wires = new Map(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들let nextId = 1;const out = [];for (let t = 1; t <= q; t++) { const parts = lines[t].trim().split(" "); let x = Number(parts[1]); let y = Number(parts[2]); if (parts[0] === "lay") { const path = [x + "," + y]; for (const ch of parts[3]) { x += STEP[ch][0]; y += STEP[ch][1]; path.push(x + "," + y); } const hit = path.find((key) => owner.has(key)); // 길 순서로 처음 막히는 칸 if (hit !== undefined) { out.push("blocked " + owner.get(hit)); // 아무 칸도 놓지 않는다 continue; } const mine = [...new Set(path)]; // 자기 길을 다시 지나는 칸은 한 번만 for (const key of mine) owner.set(key, nextId); wires.set(nextId, mine); out.push("ok " + mine.length); nextId++; } else { const key = x + "," + y; if (owner.has(key)) { const wire = owner.get(key); for (const k of wires.get(wire)) owner.delete(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다 wires.delete(wire); out.push("removed " + wire); } else { out.push("none"); } }}out.push(wires.size + " " + owner.size);console.log(out.join("\n"));
TypeScriptmain.ts · 45 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const STEP: Record<string, [number, number]> = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };const q: number = Number(lines[0]);const owner = new Map<string, number>(); // "x,y" → 전선 번호. 배열 [x, y]는 내용이 같아도 다른 열쇠라서 문자열로 만든다const wires = new Map<number, string[]>(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들let nextId = 1;const out: string[] = [];for (let t = 1; t <= q; t++) { const parts: string[] = lines[t].trim().split(" "); let x = Number(parts[1]); let y = Number(parts[2]); if (parts[0] === "lay") { const path: string[] = [x + "," + y]; for (const ch of parts[3]) { x += STEP[ch][0]; y += STEP[ch][1]; path.push(x + "," + y); } const hit: string | undefined = path.find((key: string) => owner.has(key)); // 길 순서로 처음 막히는 칸 if (hit !== undefined) { out.push("blocked " + owner.get(hit)); // 아무 칸도 놓지 않는다 continue; } const mine: string[] = [...new Set(path)]; // 자기 길을 다시 지나는 칸은 한 번만 for (const key of mine) owner.set(key, nextId); wires.set(nextId, mine); out.push("ok " + mine.length); nextId++; } else { const key: string = x + "," + y; const wire: number | undefined = owner.get(key); if (wire !== undefined) { for (const k of wires.get(wire) ?? []) owner.delete(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다 wires.delete(wire); out.push("removed " + wire); } else { out.push("none"); } }}out.push(wires.size + " " + owner.size);console.log(out.join("\n"));
JavaMain.java · 63 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.LinkedHashSet;import java.util.List;import java.util.Map;import java.util.Set;public class Main { // 두 좌표를 long 하나로 묶는다. y가 음수이면 위쪽 32비트가 모두 1이 되므로 아래 32비트만 남기고 합친다. static long key(int x, int y) { return ((long) x << 32) | (y & 0xFFFFFFFFL); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); Map<Long, Integer> owner = new HashMap<>(); // 칸 → 전선 번호 Map<Integer, List<Long>> wires = new HashMap<>(); // 전선 번호 → 그 전선이 차지한 칸들 int nextId = 1; StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { String[] parts = in.readLine().trim().split(" "); int x = Integer.parseInt(parts[1]), y = Integer.parseInt(parts[2]); if (parts[0].equals("lay")) { Set<Long> mine = new LinkedHashSet<>(); // 자기 길을 다시 지나는 칸은 한 번만 mine.add(key(x, y)); for (char ch : parts[3].toCharArray()) { if (ch == 'U') y++; else if (ch == 'D') y--; else if (ch == 'L') x--; else x++; mine.add(key(x, y)); } Integer hit = null; for (long k : mine) { // LinkedHashSet은 넣은 순서 = 길 순서 hit = owner.get(k); if (hit != null) break; } if (hit != null) { out.append("blocked ").append(hit).append('\n'); // 아무 칸도 놓지 않는다 continue; } for (long k : mine) owner.put(k, nextId); wires.put(nextId, new ArrayList<>(mine)); out.append("ok ").append(mine.size()).append('\n'); nextId++; } else { Integer wire = owner.get(key(x, y)); if (wire != null) { for (long k : wires.remove(wire)) owner.remove(k); // 열쇠를 지운다 out.append("removed ").append(wire).append('\n'); } else { out.append("none\n"); } } } out.append(wires.size()).append(' ').append(owner.size()).append('\n'); System.out.print(out); }}
C#Main.cs · 66 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int q = int.Parse(Console.ReadLine().Trim()); var owner = new Dictionary<(int, int), int>(); // 칸 → 전선 번호. 값 튜플은 값이 같으면 같은 열쇠다 var wires = new Dictionary<int, List<(int, int)>>(); // 전선 번호 → 그 전선이 차지한 칸들 int nextId = 1; var sb = new StringBuilder(); for (int t = 0; t < q; t++) { string[] parts = Console.ReadLine().Trim().Split(' '); int x = int.Parse(parts[1]), y = int.Parse(parts[2]); if (parts[0] == "lay") { var path = new List<(int, int)> { (x, y) }; foreach (char ch in parts[3]) { if (ch == 'U') y++; else if (ch == 'D') y--; else if (ch == 'L') x--; else x++; path.Add((x, y)); } int hit = 0; foreach (var cell in path) { if (owner.TryGetValue(cell, out hit)) break; // 길 순서로 처음 막히는 칸 hit = 0; } if (hit != 0) { sb.Append("blocked ").Append(hit).Append('\n'); // 아무 칸도 놓지 않는다 continue; } var mine = new List<(int, int)>(); foreach (var cell in path) { if (owner.TryAdd(cell, nextId)) mine.Add(cell); // 자기 길을 다시 지나는 칸은 한 번만 } wires[nextId] = mine; sb.Append("ok ").Append(mine.Count).Append('\n'); nextId++; } else { if (owner.TryGetValue((x, y), out int wire)) { foreach (var cell in wires[wire]) owner.Remove(cell); // 열쇠를 지운다 wires.Remove(wire); sb.Append("removed ").Append(wire).Append('\n'); } else { sb.Append("none\n"); } } } sb.Append(wires.Count).Append(' ').Append(owner.Count).Append('\n'); Console.Write(sb); }}
C++main.cpp · 59 lines
#include <iostream>#include <map>#include <string>#include <utility>#include <vector>using namespace std;int main() { int q; cin >> q; map<pair<int, int>, int> owner; // 칸 → 전선 번호. pair는 값으로 비교된다 map<int, vector<pair<int, int>>> wires; // 전선 번호 → 그 전선이 차지한 칸들 int nextId = 1; for (int t = 0; t < q; t++) { string cmd; int x, y; cin >> cmd >> x >> y; if (cmd == "lay") { string steps; cin >> steps; vector<pair<int, int>> path = {{x, y}}; for (char ch : steps) { if (ch == 'U') y++; else if (ch == 'D') y--; else if (ch == 'L') x--; else x++; path.push_back({x, y}); } int hit = 0; for (const auto& cell : path) { auto it = owner.find(cell); // owner[cell]로 물으면 없는 칸이 0으로 생겨 버린다 if (it != owner.end()) { hit = it->second; break; } } if (hit != 0) { cout << "blocked " << hit << "\n"; // 아무 칸도 놓지 않는다 continue; } vector<pair<int, int>> mine; for (const auto& cell : path) { if (owner.insert({cell, nextId}).second) mine.push_back(cell); // 자기 길을 다시 지나는 칸은 한 번만 } cout << "ok " << mine.size() << "\n"; wires[nextId] = mine; nextId++; } else { auto it = owner.find({x, y}); if (it != owner.end()) { int wire = it->second; for (const auto& cell : wires[wire]) owner.erase(cell); // 열쇠를 지운다 wires.erase(wire); cout << "removed " << wire << "\n"; } else { cout << "none\n"; } } } cout << wires.size() << " " << owner.size() << "\n"; return 0;}
Cmain.c · 99 lines
#include <stdio.h>#include <string.h>/* C에는 사전이 없어서 해시 표를 직접 만든다. 칸은 (x, y, 전선 번호)이고, 빈 칸은 state 0, 쓰는 칸은 1, 지운 자리는 2(찾을 때 건너뛰고 계속 본다). */#define SLOTS (1 << 19) /* 놓는 칸은 모두 합쳐 2,000 × 101 = 202,000개 이하라 표가 차지 않는다 */#define MAXQ 2000#define MAXLEN 100static int slot_x[SLOTS], slot_y[SLOTS], slot_id[SLOTS];static char state[SLOTS];static int wire_x[MAXQ + 1][MAXLEN + 1], wire_y[MAXQ + 1][MAXLEN + 1], wire_cells[MAXQ + 1];static unsigned hash(int x, int y) { unsigned h = (unsigned)x * 2654435761u ^ ((unsigned)y * 40503u + 0x9e3779b9u); h ^= h >> 15; return h & (SLOTS - 1);}/* (x, y)가 든 자리를 돌려준다. 없으면 -1 */static int find(int x, int y) { unsigned h = hash(x, y); while (state[h] != 0) { if (state[h] == 1 && slot_x[h] == x && slot_y[h] == y) return (int)h; h = (h + 1) & (SLOTS - 1); } return -1;}static void insert(int x, int y, int id) { unsigned h = hash(x, y); while (state[h] == 1) h = (h + 1) & (SLOTS - 1); state[h] = 1; slot_x[h] = x; slot_y[h] = y; slot_id[h] = id;}int main(void) { int q; if (scanf("%d", &q) != 1) return 0; int next_id = 1, wire_count = 0, cell_count = 0; for (int t = 0; t < q; t++) { char cmd[8]; int x, y; if (scanf("%7s %d %d", cmd, &x, &y) != 3) return 0; if (strcmp(cmd, "lay") == 0) { char steps[MAXLEN + 2]; if (scanf("%101s", steps) != 1) return 0; int len = (int)strlen(steps); int px[MAXLEN + 1], py[MAXLEN + 1]; px[0] = x; py[0] = y; for (int i = 0; i < len; i++) { if (steps[i] == 'U') y++; else if (steps[i] == 'D') y--; else if (steps[i] == 'L') x--; else x++; px[i + 1] = x; py[i + 1] = y; } int hit = 0; for (int i = 0; i <= len && hit == 0; i++) { int at = find(px[i], py[i]); /* 길 순서로 처음 막히는 칸 */ if (at >= 0) hit = slot_id[at]; } if (hit != 0) { printf("blocked %d\n", hit); /* 아무 칸도 놓지 않는다 */ continue; } int n = 0; for (int i = 0; i <= len; i++) { if (find(px[i], py[i]) >= 0) continue; /* 자기 길을 다시 지나는 칸은 한 번만 */ insert(px[i], py[i], next_id); wire_x[next_id][n] = px[i]; wire_y[next_id][n] = py[i]; n++; } wire_cells[next_id] = n; wire_count++; cell_count += n; printf("ok %d\n", n); next_id++; } else { int at = find(x, y); if (at >= 0) { int wire = slot_id[at]; for (int i = 0; i < wire_cells[wire]; i++) state[find(wire_x[wire][i], wire_y[wire][i])] = 2; wire_count--; cell_count -= wire_cells[wire]; printf("removed %d\n", wire); } else { printf("none\n"); } } } printf("%d %d\n", wire_count, cell_count); return 0;}
Craykonmain.cray · 83 lines
q = Console.ReadLine().ToNumber();owner = Dict(); // "x,y" → 전선 번호. 열쇠는 두 좌표를 쉼표로 이은 문자열wires = Dict(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들nextId = 1;for (t = 0; t < q; t++){ parts = Console.ReadLine().Trim().Split(" "); x = parts[1].ToNumber(); y = parts[2].ToNumber(); if (parts[0] == "lay") { path = ["" + x + "," + y]; steps = parts[3]; for (i = 0; i < steps.Length; i++) { ch = steps.Substring(i, 1); if (ch == "U") { y = y + 1; } else if (ch == "D") { y = y - 1; } else if (ch == "L") { x = x - 1; } else { x = x + 1; } path.Add("" + x + "," + y); } hit = 0; foreach (key in path) { if (owner.Contains(key)) { hit = owner[key]; // 길 순서로 처음 막히는 칸 break; } } if (hit != 0) { Console.WriteLine("blocked " + hit); // 아무 칸도 놓지 않는다 } else { mine = []; foreach (key in path) { if (!owner.Contains(key)) { owner[key] = nextId; mine.Add(key); } } wires[nextId] = mine; Console.WriteLine("ok " + mine.Count); nextId = nextId + 1; } } else { key = "" + x + "," + y; if (owner.Contains(key)) { wire = owner[key]; foreach (k in wires[wire]) { owner.Remove(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다 } wires.Remove(wire); Console.WriteLine("removed " + wire); } else { Console.WriteLine("none"); } }}Console.WriteLine(wires.Count + " " + owner.Count);