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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
q = コンソール.行読み().数に();owner = 辞書(); // "x,y" → 전선 번호. 열쇠는 두 좌표를 쉼표로 이은 문자열wires = 辞書(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들nextId = 1;繰り返す (t = 0; t < q; t++){ parts = コンソール.行読み().空白除去().分ける(" "); x = parts[1].数に(); y = parts[2].数に(); もし (parts[0] == "lay") { path = ["" + x + "," + y]; steps = parts[3]; 繰り返す (i = 0; i < steps.長さ; i++) { ch = steps.切り出す(i, 1); もし (ch == "U") { y = y + 1; } でなければ もし (ch == "D") { y = y - 1; } でなければ もし (ch == "L") { x = x - 1; } でなければ { x = x + 1; } path.追加("" + x + "," + y); } hit = 0; それぞれ (key の中 path) { もし (owner.含む(key)) { hit = owner[key]; // 길 순서로 처음 막히는 칸 抜ける; } } もし (hit != 0) { コンソール.書く("blocked " + hit); // 아무 칸도 놓지 않는다 } でなければ { mine = []; それぞれ (key の中 path) { もし (!owner.含む(key)) { owner[key] = nextId; mine.追加(key); } } wires[nextId] = mine; コンソール.書く("ok " + mine.個数); nextId = nextId + 1; } } でなければ { key = "" + x + "," + y; もし (owner.含む(key)) { wire = owner[key]; それぞれ (k の中 wires[wire]) { owner.取り除く(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다 } wires.取り除く(wire); コンソール.書く("removed " + wire); } でなければ { コンソール.書く("none"); } }}コンソール.書く(wires.個数 + " " + owner.個数);