referencesP0262

Name tags pointing at the same list

Follow a small ledger where name tags point at lists of integers. Each name always points at exactly one list, and several names may point at the same list. The first line gives the number of commands q, and the next q lines give one command each. - new x: make a new empty list and let name x point at it. - let x y: let x point at the very list that y points at.
The list is not copied. - copy x y: make a new list holding the current contents of the list y points at, and let x point at that new list. - push x v: append v to the end of the list x points at.
Every name pointing at that list sees the change. - same x y: print yes on its own line if x and y point at the same list, otherwise no.
Two different lists with equal contents are no. - print x: on one line, print how many numbers the list x points at holds, followed by those numbers in insertion order, separated by single spaces.
If the list is empty, print just 0. When new, let or copy makes x point at another list, the contents of the list x pointed at before do not change. Other names that pointed at that list keep pointing at it. x and y may be the same name.
let x x changes nothing, and copy x x makes x point at a new copy of its current contents. If x is a name seen for the first time, new, let and copy create it. Try storing a reference to each list rather than a copy of the list per name.

Input: 1 ≤ q ≤ 2,000.
Names are 1–10 lowercase letters or digits.
v is an integer from 0 to 1,000,000 (no leading zeros).
The y of let/copy and the names in push/same/print were already created by an earlier new/let/copy.
There is at least one same or print, and the whole output is at most 200,000 characters
Output: One line per same and print, in command order

Example 1 · stdin

12
new a
push a 1
let b a
push b 2
copy c a
same a b
same a c
push c 3
new a
push a 9
print b
print c

stdout

yes
no
2 1 2
3 1 2 3

Example 2 · stdin

8
new x
new y
same x y
let y x
same y x
copy x x
same x y
print y

stdout

no
yes
no
0

main.py Programming language Runtime version

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 takes all 8 languages, but how you get 'pointing' differs.
Python list, JavaScript/TypeScript arrays, Java ArrayList, C# List<int> and Craykon lists are all references, so storing one in a map or assigning it just adds one more thing pointing at the same list.
So let is a plain assignment, and only copy copies on purpose: Python a.copy()/a[:]/list(a), JS/TS [...a]/a.slice(), Java new ArrayList<>(a), C# new List<int>(a), Craykon a.GetRange(0, a.Count) (a.부분목록(0, a.개수)).
C++ std::vector is the opposite: it is a value, so names[x] = names[y] copies the whole list.
To share one list, store std::shared_ptr<std::vector<int>> (or an index into a pool of lists).
In C, storing the List struct itself means assignment copies the buffer pointer and the length, so numbers pushed through one copy are not counted by the other.
Store List * pointers instead.
'same' asks about identity, which is easy to confuse with comparing contents: Python is (== compares contents), Java == (equals compares contents), C# ReferenceEquals (== on List is also a reference comparison), JS/TS ===, C/C++ address comparison (== on shared_ptr compares addresses, on vector compares contents), and Craykon == on lists asks whether they are the same list.
Four traps: ① copying in let makes later pushes visible on one side only.
② not copying in copy makes both names change one list together.
③ comparing two empty lists by contents says they are the same.
④ implementing let x y as 'overwrite the contents of x's list with y's contents' also changes every other name that shared x's list.
Re-pointing (assignment) and modifying (changing contents) are different things.

Pythonmain.py · 23 lines

import sys lines = sys.stdin.read().split("\n")q = int(lines[0])names = {}  # 이름 → 그 이름이 가리키는 목록(참조)out = []for line in lines[1 : q + 1]:    p = line.split()    cmd = p[0]    if cmd == "new":        names[p[1]] = []    elif cmd == "let":        names[p[1]] = names[p[2]]  # 같은 목록을 가리킨다(복사하지 않는다)    elif cmd == "copy":        names[p[1]] = names[p[2]].copy()  # 내용만 같은 새 목록    elif cmd == "push":        names[p[1]].append(int(p[2]))    elif cmd == "same":        out.append("yes" if names[p[1]] is names[p[2]] else "no")  # == 는 내용을 비교한다    else:        a = names[p[1]]        out.append(" ".join(map(str, [len(a)] + a)))print("\n".join(out))

JavaScriptmain.js · 17 lines

const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const names = new Map(); // 이름 → 그 이름이 가리키는 배열(참조)const out = [];for (let i = 1; i <= q; i++) {  const [cmd, x, y] = lines[i].trim().split(" ");  if (cmd === "new") names.set(x, []);  else if (cmd === "let") names.set(x, names.get(y)); // 같은 배열을 가리킨다  else if (cmd === "copy") names.set(x, [...names.get(y)]); // 내용만 같은 새 배열  else if (cmd === "push") names.get(x).push(Number(y));  else if (cmd === "same") out.push(names.get(x) === names.get(y) ? "yes" : "no"); // 배열의 ===는 같은 것인지 본다  else {    const a = names.get(x);    out.push([a.length, ...a].join(" "));  }}console.log(out.join("\n"));

TypeScriptmain.ts · 20 lines

import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const names = new Map<string, number[]>(); // 이름 → 그 이름이 가리키는 배열(참조)const out: string[] = [];const get = (name: string): number[] => names.get(name)!;for (let i = 1; i <= q; i++) {  const [cmd, x, y] = lines[i].trim().split(" ");  if (cmd === "new") names.set(x, []);  else if (cmd === "let") names.set(x, get(y)); // 같은 배열을 가리킨다  else if (cmd === "copy") names.set(x, [...get(y)]); // 내용만 같은 새 배열  else if (cmd === "push") get(x).push(Number(y));  else if (cmd === "same") out.push(get(x) === get(y) ? "yes" : "no"); // 배열의 ===는 같은 것인지 본다  else {    const a = get(x);    out.push([a.length, ...a].join(" "));  }}console.log(out.join("\n"));

JavaMain.java · 32 lines

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; public class Main {    public static void main(String[] args) throws Exception {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int q = Integer.parseInt(in.readLine().trim());        Map<String, List<Integer>> names = new HashMap<>(); // 이름 → 그 이름이 가리키는 목록(참조)        StringBuilder out = new StringBuilder();        for (int i = 0; i < q; i++) {            String[] p = in.readLine().trim().split(" ");            switch (p[0]) {                case "new" -> names.put(p[1], new ArrayList<>());                case "let" -> names.put(p[1], names.get(p[2])); // 같은 목록을 가리킨다                case "copy" -> names.put(p[1], new ArrayList<>(names.get(p[2]))); // 내용만 같은 새 목록                case "push" -> names.get(p[1]).add(Integer.parseInt(p[2]));                case "same" -> out.append(names.get(p[1]) == names.get(p[2]) ? "yes" : "no").append('\n'); // ==는 같은 객체인지                default -> {                    List<Integer> a = names.get(p[1]);                    out.append(a.size());                    for (int v : a) out.append(' ').append(v);                    out.append('\n');                }            }        }        System.out.print(out);    }}

C#Main.cs · 32 lines

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int q = int.Parse(Console.ReadLine()!.Trim());        var names = new Dictionary<string, List<int>>(); // 이름 → 그 이름이 가리키는 목록(참조)        var sb = new StringBuilder();        for (int i = 0; i < q; i++)        {            string[] p = Console.ReadLine()!.Trim().Split(' ');            switch (p[0])            {                case "new": names[p[1]] = new List<int>(); break;                case "let": names[p[1]] = names[p[2]]; break;                    // 같은 목록을 가리킨다                case "copy": names[p[1]] = new List<int>(names[p[2]]); break;    // 내용만 같은 새 목록                case "push": names[p[1]].Add(int.Parse(p[2])); break;                case "same": sb.Append(ReferenceEquals(names[p[1]], names[p[2]]) ? "yes" : "no").Append('\n'); break;                default:                    List<int> a = names[p[1]];                    sb.Append(a.Count);                    foreach (int v in a) sb.Append(' ').Append(v);                    sb.Append('\n');                    break;            }        }        Console.Write(sb);    }}

C++main.cpp · 40 lines

#include <iostream>#include <map>#include <memory>#include <string>#include <vector> using List = std::vector<int>; int main() {    std::ios::sync_with_stdio(false);    int q;    std::cin >> q;    // vector를 그대로 담으면 대입할 때마다 통째로 복사된다. shared_ptr를 담아 같은 목록을 가리키게 한다    std::map<std::string, std::shared_ptr<List>> names;    for (int i = 0; i < q; i++) {        std::string cmd, x, y;        std::cin >> cmd >> x;        if (cmd == "new") {            names[x] = std::make_shared<List>();        } else if (cmd == "let") {            std::cin >> y;            names[x] = names[y]; // 포인터만 복사: 같은 목록        } else if (cmd == "copy") {            std::cin >> y;            names[x] = std::make_shared<List>(*names[y]); // 내용을 복사한 새 목록        } else if (cmd == "push") {            int v;            std::cin >> v;            names[x]->push_back(v);        } else if (cmd == "same") {            std::cin >> y;            std::cout << (names[x] == names[y] ? "yes" : "no") << '\n'; // shared_ptr의 ==는 주소 비교        } else {            const List& a = *names[x];            std::cout << a.size();            for (int v : a) std::cout << ' ' << v;            std::cout << '\n';        }    }}

Cmain.c · 71 lines

#include <stdio.h>#include <stdlib.h>#include <string.h> typedef struct {    int *items;    int len, cap;} List; static List *new_list(void) {    List *l = malloc(sizeof *l);    l->len = 0;    l->cap = 4;    l->items = malloc(sizeof(int) * l->cap);    return l;} static void push(List *l, int v) {    if (l->len == l->cap) {        l->cap *= 2;        l->items = realloc(l->items, sizeof(int) * l->cap);    }    l->items[l->len++] = v;} /* 이름표: 이름마다 목록의 주소(List *)를 담는다. 구조체를 통째로 담으면 복사본이 된다 */static char names[2000][11];static List *refs[2000];static int count = 0; static int find(const char *name) {    for (int i = 0; i < count; i++)        if (strcmp(names[i], name) == 0) return i;    strcpy(names[count], name);    refs[count] = NULL;    return count++;} int main(void) {    int q;    scanf("%d", &q);    for (int i = 0; i < q; i++) {        char cmd[8], x[11], y[11];        scanf("%7s %10s", cmd, x);        int a = find(x);        if (strcmp(cmd, "new") == 0) {            refs[a] = new_list();        } else if (strcmp(cmd, "let") == 0) {            scanf("%10s", y);            refs[a] = refs[find(y)]; /* 주소만 옮긴다: 같은 목록 */        } else if (strcmp(cmd, "copy") == 0) {            scanf("%10s", y);            List *src = refs[find(y)], *l = new_list();            for (int k = 0; k < src->len; k++) push(l, src->items[k]);            refs[a] = l;        } else if (strcmp(cmd, "push") == 0) {            int v;            scanf("%d", &v);            push(refs[a], v);        } else if (strcmp(cmd, "same") == 0) {            scanf("%10s", y);            puts(refs[a] == refs[find(y)] ? "yes" : "no"); /* 주소가 같으면 같은 목록 */        } else {            List *l = refs[a];            printf("%d", l->len);            for (int k = 0; k < l->len; k++) printf(" %d", l->items[k]);            putchar('\n');        }    }    return 0;}

Craykonmain.cray · 38 lines

q = Console.ReadLine().ToNumber();이름표 = Dict(); // 이름 → 그 이름이 가리키는 목록. 목록은 참조라서 담아도 복사되지 않는다for (i = 0; i < q; i++){    p = Console.ReadLine().Trim().Split();    x = p[1];    switch (p[0])    {        case "new":            이름표[x] = [];            break;        case "let":            이름표[x] = 이름표[p[2]]; // 같은 목록을 가리킨다            break;        case "copy":            원본 = 이름표[p[2]];            이름표[x] = 원본.GetRange(0, 원본.Count); // 내용만 같은 새 목록            break;        case "push":            이름표[x].Add(p[2].ToNumber());            break;        case "same":            // 목록끼리 ==는 같은 목록인지 묻는다(내용 비교가 아니다)            Console.WriteLine(이름표[x] == 이름표[p[2]] ? "yes" : "no");            break;        default:            a = 이름표[x];            if (a.Count == 0)            {                Console.WriteLine("0");            }            else            {                Console.WriteLine(a.Count + " " + a.Join(" "));            }            break;    }}