Introducción a conjuntos y mapas

Introducción

Recursos
Fuente	Recurso	Notas
IUSACO	4.4 - Sets & Maps	este módulo se basa en esto
CPH	4.2, 4.3 - Sets, Maps	cubre material similar

Un conjunto (set) es una colección de elementos únicos. Los conjuntos tienen tres métodos principales:

uno para agregar un elemento
uno para eliminar un elemento
uno para comprobar si un elemento está presente

Un mapa (map) es una colección de entradas, cada una formada por una clave y un valor. En un mapa, todas las claves deben ser únicas (es decir, forman un conjunto), pero los valores se pueden repetir. Los mapas tienen tres métodos principales:

uno para agregar un par clave-valor
uno para eliminar un par clave-valor
uno para obtener el valor de una clave dada

C++ y Java tienen dos implementaciones de conjuntos y mapas: una usa ordenamiento y la otra usa hashing. La implementación de conjuntos y mapas de Python usa hashing.

Conjuntos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Distinct Numbers	Fácil	Sorting, Set	Solución

Conjuntos ordenados

Los conjuntos ordenados almacenan los elementos en orden. Todos los métodos principales (agregar, eliminar y consultar) corren en tiempo $\mathcal{O}(\log N)$ en el peor caso, donde $N$ es la cantidad de elementos del conjunto.

C++JavaPython

Los conjuntos ordenados se implementan en C++ con std::set del header <set>. Algunas operaciones básicas sobre un std::set llamado s incluyen:

s.insert(x), que agrega el elemento x a s si aún no está.
s.erase(x), que elimina el elemento x de s si está presente.
s.count(x), que devuelve 1 si s contiene x y 0 si no.

También se puede iterar un conjunto en orden usando un bucle for-each.


#include <iostream>
#include <set>
 
using namespace std;
 
void demo() {
	set<int> s;
	s.insert(1);                 // [1]
	s.insert(4);                 // [1, 4]
	s.insert(2);                 // [1, 2, 4]
	s.insert(1);                 // no hace nada porque 1 ya está en el conjunto
	cout << s.count(1) << endl;  // 1
	s.erase(1);                  // [2, 4]
	cout << s.count(5) << endl;  // 0
	s.erase(0);                  // no hace nada porque 0 no estaba en el conjunto
	s.insert(6);                 // [2, 4, 6]
 
	// Imprime 2, 4 y 6 separados por espacios
	for (int element : s) { cout << element << " "; }
}

Los conjuntos ordenados se implementan en Java con la clase TreeSet.

TreeSet incluye todas las operaciones de HashSet, y además algunas extra. Ver el módulo Más operaciones sobre conjuntos ordenados para más detalle.

Se puede iterar un TreeSet en orden usando un bucle for-each.


Set<Integer> set = new TreeSet<>();
set.add(1);  // {1}
set.add(4);  // {1, 4}
set.add(2);  // {1, 2, 4}
 
/*
 * Salida:
 * 1
 * 2
 * 4
 */
 
for (int element : set) { System.out.println(element); }

Conjuntos hash

Los conjuntos hash (hashsets) almacenan los elementos usando hashing. A grandes rasgos, un conjunto hash consiste en cierta cantidad $B$ de cubetas (buckets), y cada elemento se asigna a una cubeta mediante una función de hash. Si $B\approx N$ y la función de hash mapea de forma independiente cada elemento distinto a una cubeta uniforme al azar, entonces no se espera que ninguna cubeta contenga muchos elementos, y todos los métodos principales corren en tiempo $\mathcal O(1)$ esperado.

C++JavaPython

Los conjuntos hash se implementan en C++ con std::unordered_set del header <unordered_set>.


#include <iostream>
#include <unordered_set>
 
using namespace std;
 
void demo() {
	unordered_set<int> s;
	s.insert(1);                 // {1}
	s.insert(4);                 // {1, 4}
	s.insert(2);                 // {1, 2, 4}
	s.insert(1);                 // no hace nada porque 1 ya está en el conjunto
	cout << s.count(1) << endl;  // 1
	s.erase(1);                  // {2, 4}
	cout << s.count(5) << endl;  // 0
	s.erase(0);                  // no hace nada porque 0 no estaba en el conjunto
	s.insert(6);                 // {2, 4, 6}
 
	// Imprime 6, 2 y 4 separados por espacios (no en orden)
	for (int element : s) { cout << element << " "; }
}

Los conjuntos hash funcionan con tipos primitivos, pero requieren una función de hash personalizada para estructuras/clases como vectors y pairs.

Los conjuntos hash se implementan en Java con la clase HashSet (de la librería java.util).

Algunas operaciones sobre un HashSet llamado set incluyen:

set.add(x), que agrega el elemento x a set si aún no está.
set.remove(x), que elimina el elemento x de set si está presente.
set.contains(x), que comprueba si set contiene el elemento x.

Los conjuntos hash funcionan con tipos primitivos y sus wrappers de objetos, pero requieren una función de hash personalizada para clases propias.


Set<Integer> set = new HashSet<>();
set.add(1);  // {1}
set.add(4);  // {1, 4}
set.add(2);  // {1, 4, 2}
set.add(1);  // {1, 4, 2}
// add no hizo nada porque 1 ya estaba en el conjunto
System.out.println(set.contains(1));  // true
set.remove(1);                        // {4, 2}
System.out.println(set.contains(5));  // false
set.remove(0);                        // no hace nada porque 0 no estaba en el conjunto

El set incorporado de Python usa hashing para soportar inserción, eliminación y búsquedas en $\mathcal{O}(1)$ . Algunas operaciones sobre un set de Python llamado s incluyen:

s.add(x): agrega el elemento x a s si aún no está
s.remove(x): elimina el elemento x de set si está presente
x in s: comprueba si s contiene el elemento x


s = set()
s.add(1)  # {1}
s.add(4)  # {1, 4}
s.add(2)  # {1, 4, 2}
s.add(1)  # {1, 4, 2}
# add no hizo nada porque 1 ya estaba en el conjunto
print(1 in s)  # True
s.remove(1)  # {4, 2}
print(5 in s)  # False
s.remove(0)  # {4, 2}
# si el elemento a eliminar no existe, no pasa nada

Solución - Distinct Numbers

Este problema pide calcular la cantidad de valores distintos en una lista dada.

Método 1 - Conjunto ordenado

Como los conjuntos solo guardan una copia de cada valor, podemos insertar todos los números en un conjunto y luego imprimir el tamaño del conjunto.

C++JavaPython


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	set<int> distinctNumbers;
	for (int i = 0; i < n; i++) {
		int number;
		cin >> number;
		distinctNumbers.insert(number);
	}
 
	cout << distinctNumbers.size() << endl;
}


// Source: Daniel
 
import java.io.*;
import java.util.*;
 
public class DistinctNumbers {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		Set<Integer> set = new TreeSet<>();
		for (int i = 0; i < n; i++) { set.add(io.nextInt()); }
		io.println(set.size());
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Método 2 - Conjunto hash

C++JavaPython

Igual que el método 1, pero reemplazando el conjunto ordenado por un conjunto hash.


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	unordered_set<int> distinctNumbers;
	for (int i = 0; i < n; i++) {
		int number;
		cin >> number;
		distinctNumbers.insert(number);
	}
 
	cout << distinctNumbers.size() << endl;
}

Sin embargo, esto falla en un caso de prueba diseñado específicamente para que unordered_set corra en tiempo $\Theta(N^2)$ . Para evitarlo, se puede pasar a set o usar una función de hash personalizada.

Igual que el método 1, pero reemplazando el conjunto ordenado por un conjunto hash.


// Source: Daniel
 
import java.io.*;
import java.util.*;
 
public class DistinctNumbers {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < n; i++) { set.add(io.nextInt()); }
		io.println(set.size());
		io.close();
	}
 
	// CodeSnip{Kattio}
}


n = int(input())  # no se usa
nums = [int(x) for x in input().split()]
distinct_nums = set(nums)
print(len(distinct_nums))

O se puede hacer de forma más concisa omitiendo la creación de la lista y usando una comprensión de conjunto directamente:


n = int(input())  # no se usa
distinct_nums = {int(x) for x in input().split()}
print(len(distinct_nums))

Sin embargo, es posible construir un caso de prueba que haga que la solución de arriba corra en tiempo $\Theta(N^2)$ , así que esta solución no recibe puntaje completo.

Generador de caso hack


# source: https://foss.heptapod.net/pypy/pypy/-/issues/3725
import time
 
 
def anti_hash_hack(n: int, cpython: bool = False, for_set=False):
	"""
	Args:
	    entero n > 0
	    cpython: CPython o Pypy
	    for_set: set o dict
	Output: lista A de longitud n
	tal que 1 <= A[i] <= 2**(n.bit_length() + 2) + 10
	"""
	pow2 = 2 ** (n.bit_length() + 2)
 
	A = []
 
	def add_all(x):
		for i in range(10 if (cpython and for_set) else 1):
			A.append(x + i)
 
	add_all(pow2 + 1)
	i = 6 if cpython else 7
	while len(A) < n // 2:
		assert i > 0
		add_all(i)
		i = (5 * i + 1) % pow2
 
	while len(A) < n:
		A.append(1)
 
	return A
 
 
N = 200000
A = anti_hash_hack(N, False, False)
 
# https://cses.fi/problemset/task/1640/
print_test = False
if print_test:
	print(N, 1)
	print(" ".join(str(x) for x in A))
 
do_test = True
if do_test:
	print("Creating set:")
	start = time.time()
	set(A)
	print("Done", time.time() - start)
 
	print("Creating dict:")
	start = time.time()
	my_dict = {}
	for i in range(N):
		my_dict[A[i]] = i
	print("Done", time.time() - start)

Una forma de evitarlo con alta probabilidad es incorporar aleatoriedad; ver este comentario para más información.


import random
 
RANDOM = random.randrange(2**62)
 
 
def Wrapper(x):
	return x ^ RANDOM
 
 
n = int(input())  # no se usa
distinct_nums = {Wrapper(int(x)) for x in input().split()}
print(len(distinct_nums))

Otra forma (menos eficiente) es usar strings en lugar de enteros, ya que la función de hash de strings está aleatorizada.


n = int(input())  # no se usa
distinct_nums = set(input().split())
print(len(distinct_nums))

Método 3 - Ordenamiento

Ver la solución que usa ordenamiento.

Mapas

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Associative Array	Fácil	Map	en el módulo

En los mapas ordenados, los pares se ordenan por clave. Como en los conjuntos ordenados, todos los métodos principales corren en tiempo $\mathcal{O}(\log N)$ en el peor caso, donde $N$ es la cantidad de pares del mapa.

En las tablas hash, los pares se hashean a cubetas según la clave y, como en los conjuntos hash, todos los métodos principales corren en tiempo $\mathcal O(1)$ esperado bajo ciertos supuestos sobre la función de hash.

C++JavaPython

En C++, los mapas ordenados se implementan con std::map y las tablas hash con std::unordered_map.

Algunas operaciones sobre un std::map y un std::unordered_map llamados m incluyen:

m[key], que devuelve una referencia al valor asociado a la clave key.
- Si key no está en el mapa, el valor asociado a key se construye con el constructor por defecto del tipo del valor. Por ejemplo, si el tipo del valor es int, entonces llamar a m[key] para una clave que no está en el mapa asigna el valor 0 a esa clave. Como otro ejemplo, si el tipo del valor es std::string, entonces llamar a m[key] para una clave que no está en el mapa asigna el string vacío a esa clave. Más discusión sobre qué ocurre en este caso se puede encontrar aquí .
- Como alternativa, m.at(key) se comporta igual que m[key] si key está en m, pero lanza una excepción en caso contrario.
- m[key] = value asigna el valor value a la clave key.
m.count(key), que devuelve la cantidad de veces que la clave está en el mapa (uno o cero), y por lo tanto comprueba si una clave existe en el mapa.
m.erase(key), que elimina la entrada del mapa asociada a la clave indicada si la clave estaba presente en el mapa.


#include <iostream>
#include <map>
 
using namespace std;
 
void demo() {
	map<int, int> m;
	m[1] = 5;                    // [(1, 5)]
	m[3] = 14;                   // [(1, 5); (3, 14)]
	m[2] = 7;                    // [(1, 5); (2, 7); (3, 14)]
	m[0] = -1;                   // [(0, -1); (1, 5); (2, 7); (3, 14)]
	m.erase(2);                  // [(0, -1); (1, 5); (3, 14)]
	cout << m[1] << endl;        // 5
	cout << m.count(7) << endl;  // 0
	cout << m.count(1) << endl;  // 1
	cout << m[2] << endl;        // 0
}

En Java, los mapas ordenados se implementan con TreeMap y las tablas hash con HashMap.

Tanto en TreeMap como en HashMap, el método put(key, value) asigna un valor a una clave y coloca el par clave-valor en el mapa. El método get(key) devuelve el valor asociado a la clave. El método containsKey(key) comprueba si una clave existe en el mapa. Por último, remove(key) elimina la entrada del mapa asociada a la clave indicada.


Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(1, 5);                           // [(1, 5)]
map.put(3, 14);                          // [(1, 5); (3, 14)]
map.put(2, 7);                           // [(1, 5); (2, 7); (3, 14)]
map.remove(2);                           // [(1, 5); (3, 14)]
System.out.println(map.get(1));          // 5
System.out.println(map.containsKey(7));  // false
System.out.println(map.containsKey(1));  // true

De forma coloquial, en Python las tablas hash se llaman dicts.


d = {}
d[1] = 5  # {1: 5}
d[3] = 14  # {1: 5, 3: 14}
d[2] = 7  # {1: 5, 2: 7, 3: 14}
del d[2]  # {1: 5, 3: 14}
print(d[1])  # 5
print(7 in d)  # False
print(1 in d)  # True

Iterar sobre mapas

C++JavaPython

Un std::map almacena las entradas como pares de la forma {key, value}. Para iterar sobre mapas se puede usar un bucle for. La palabra clave auto alcanza para iterar sobre cualquier tipo de par (aquí, auto sustituye a pair<int, int>).


// Ambos imprimen lo mismo
for (const auto &x : m) { cout << x.first << " " << x.second << endl; }
for (auto x : m) { cout << x.first << " " << x.second << endl; }

El primer método (iterar sobre referencias const) suele preferirse al segundo porque el segundo hace una copia de cada elemento que recorre. Además, se puede pasar por referencia al iterar un mapa, lo que permite modificar los valores (pero no las claves) de los pares almacenados:


for (auto &x : m) {
	x.second = 1234;  // Cambiar todos los valores a 1234
}

Para iterar sobre mapas se puede usar un bucle for-each sobre las claves:


for (int k : m.keySet()) { System.out.println(k + " " + m.get(k)); }

También se puede usar un bucle for-each sobre las entradas:


for (Map.Entry entry : m.entrySet()) {
	System.out.println(entry.getKey() + " " + entry.getValue());
}

También es posible cambiar los valores mientras se itera sobre las claves (o sobre los valores mismos, si son mutables):


for (int k : m.keySet()) {
	m.put(k, 1234);  // Cambiar todos los valores a 1234
}

Para iterar sobre dicts hay tres opciones, todas con bucles for. En Python 3.6+ los dicts se recorren en el mismo orden de inserción. Se puede iterar sobre las claves:


for key in d:
	print(key)

Sobre los valores:


for value in d.values():
	print(value)

E incluso sobre pares clave-valor:


for key, value in d.items():
	print(key, value)

También es posible cambiar los valores mientras se itera sobre las claves (o sobre los valores mismos, si son mutables):


for key in d:
	d[key] = 1234  # Cambiar todos los valores a 1234

Aunque se pueden cambiar los valores de un mapa al iterarlo (como se mostró arriba), en general es mala idea insertar o eliminar elementos de un mapa mientras se itera.

PythonC++Java

Por ejemplo, el siguiente código intenta eliminar todas las entradas de un mapa, pero produce un error de ejecución.


d = {i: i for i in range(10)}
 
for i in d:
	del d[i]


Traceback (most recent call last):
  File "test.py", line 3, in <module>
    for i in d:
RuntimeError: dictionary changed size during iteration

Una forma de evitarlo es crear un mapa nuevo.


d = {i: i for i in range(10)}
 
# solo incluye cada tercer elemento
d_new = dict(item for i, item in enumerate(d.items()) if i % 3 == 0)
 
print("new dict:", d_new)  # new dict: {0: 0, 3: 3, 6: 6, 9: 9}

Otra es mantener una lista de todas las claves que se quieren eliminar y eliminarlas después de terminar la iteración:


d = {i: i for i in range(10)}
 
# elimina cada tercer elemento
to_remove = {key for i, key in enumerate(d) if i % 3 == 0}
 
for key in to_remove:
	del d[key]
 
print("new dict:", d)  # new dict: {1: 1, 2: 2, 4: 4, 5: 5, 7: 7, 8: 8}

Por ejemplo, el siguiente código intenta eliminar todas las entradas de un mapa, pero produce un fallo de segmentación.


map<int, int> m;
 
for (int i = 0; i < 10; ++i) m[i] = i;
 
for (auto &it : m) {
	cout << "Current Key: " << it.first << endl;
 
	m.erase(it.first);
}

La razón es que «los iteradores, punteros y referencias que apuntan a elementos eliminados por la función [quedan] invalidados» (como indica la documentación de erase), aunque los iteradores están fuera del alcance de este módulo.

Una forma de evitarlo es crear un mapa nuevo en lugar de eliminar del anterior.


map<int, int> m, M;
 
for (int i = 0; i < 10; ++i) m[i] = i;
 
int current_iteration = 0;
 
for (const auto &it : m) {
	// solo incluye cada tercer elemento
	if (current_iteration % 3 == 0) { M[it.first] = it.second; }
 
	current_iteration++;
}
 
swap(m, M);
 
cout << "Entries:" << endl;
for (const auto &it : m) { cout << it.first << " " << it.second << endl; }
/*
 * Entries:
 * 0 0
 * 3 3
 * 6 6
 * 9 9
 */

Otra es mantener una lista de todas las claves que se quieren borrar y borrarlas después de terminar la iteración.


map<int, int> m;
for (int i = 0; i < 10; ++i) { m[i] = i; }
 
vector<int> to_erase;
int current_iteration = 0;
 
for (const auto &it : m) {
	// elimina cada tercer elemento
	if (current_iteration % 3 == 0) { to_erase.push_back(it.first); }
 
	current_iteration++;
}
 
for (int key : to_erase) { m.erase(key); }
 
cout << "Remaining entries:" << endl;
for (const auto &it : m) { cout << it.first << " " << it.second << endl; }
 
/*
 * Remaining entries:
 * 1 1
 * 2 2
 * 4 4
 * 5 5
 * 7 7
 * 8 8
 */

Modificar una Collection (Set, Map, etc.) en medio de un bucle for-each provoca una ConcurrentModificationException . Ver el siguiente fragmento como ejemplo:


Map<Integer, Integer> m = new TreeMap<>();
// m empieza como {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);
 
for (int key : m.keySet()) {
	m.remove(key);  // ¡se lanza ConcurrentModificationException!
}

Una solución es usar Iterator y el método .remove() para eliminar elementos mientras se recorren, como en el siguiente fragmento:


Map<Integer, Integer> m = new TreeMap<>();
// m empieza como {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);
 
Iterator<Map.Entry<Integer, Integer>> iter = m.entrySet().iterator();
while (iter.hasNext()) {
	int key = iter.next().getKey();
	if (key == 0 || key == 2) { iter.remove(); }
}
 
// m termina como {1: 1}
System.out.println("Remaining Entries:");
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
	System.out.println(entry.getKey() + " " + entry.getValue());
}

Sin embargo, Iterator está fuera del alcance de este módulo.

La opción más fácil (en la mayoría de los casos) si se quieren eliminar/insertar varias entradas a la vez es usar los métodos .addAll(c) o .removeAll(c) del contenedor. Eso significa poner todos los elementos que se quieren eliminar (o agregar) en una Collection nueva, y luego usar esa Collection nueva como parámetro de .addAll(c) o .removeAll(c) sobre la Collection original. Ver el siguiente fragmento como ejemplo (funciona de forma equivalente al código de arriba):


Map<Integer, Integer> m = new TreeMap<>();
// m empieza como {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);
 
Set<Integer> keysToRemove = new TreeSet<>();
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
	int key = entry.getKey();
	if (key == 0 || key == 2) { keysToRemove.add(key); }
}
 
// elimina todas las entradas cuya clave está en keysToRemove
m.keySet().removeAll(keysToRemove);
 
// m termina como {1: 1}
System.out.println("Remaining Entries:");
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
	System.out.println(entry.getKey() + " " + entry.getValue());
}

Solución - Associative Array

Para resolver este problema de forma eficiente, hace falta una estructura de datos que pueda:

Asignar un valor a cualquier índice k (donde k puede ser tan grande como $10^{18}$ ).
Recuperar el valor en cualquier índice k de forma rápida.

Un arreglo común no sirve porque los índices pueden ser enormes, lo que hace imposible reservar memoria suficiente. Sin embargo, como todos los valores empiezan en 0 y solo un subconjunto pequeño de índices se asignará o consultará, podemos usar un mapa (también llamado arreglo asociativo o diccionario) para guardar solo los índices a los que se les asignó un valor.

Cuando llega una consulta 0 k v, asignamos a[k] = v en el mapa.
Cuando llega una consulta 1 k, imprimimos a[k] si existe en el mapa, o 0 en caso contrario.

Este enfoque es eficiente porque ambas operaciones son rápidas en mapas, y solo guardamos las claves que realmente se usan.

Nótese que usamos enteros de 64 bits porque $k$ y $v$ pueden ser grandes.

C++JavaPython


#include <iostream>
#include <map>
 
using namespace std;
 
int main() {
	int query_num;
	cin >> query_num;
	map<long long, long long> a;  // Mapa para guardar solo los índices asignados
	for (int q = 0; q < query_num; q++) {
		int t;
		cin >> t;
		if (t == 0) {
			long long k, v;
			cin >> k >> v;
			a[k] = v;
		} else if (t == 1) {
			long long k;
			cin >> k;
			// Si k no está en el mapa, operator[] devuelve 0 por defecto
			cout << a[k] << '\n';
		}
	}
}


import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int queryNum = Integer.parseInt(br.readLine());
		// Mapa para guardar los índices asignados
		HashMap<Long, Long> a = new HashMap<Long, Long>();
		for (int i = 0; i < queryNum; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long t = Long.parseLong(st.nextToken());
			long k = Long.parseLong(st.nextToken());
			if (t == 0) {
				long v = Long.parseLong(st.nextToken());
				a.put(k, v);
			} else if (t == 1) {
				// Si k no está, devolver 0
				System.out.println(a.getOrDefault(k, 0L));
			}
		}
	}
}

Lamentablemente, la solución directa falla en algunos casos de prueba diseñados específicamente para que los dicts de Python corran lento:


a = dict()  # Diccionario para guardar los índices asignados
for _ in range(int(input())):
	nums = list(map(int, input().split()))
	if nums[0] == 0:
		a[nums[1]] = nums[2]
	elif nums[0] == 1:
		# Imprimir a[k] si está, si no 0
		print(a.get(nums[1], 0))

Para pasar todos los tests, se puede usar una de las soluciones mencionadas para set.


import random
 
RANDOM = random.randrange(2**62)
 
 
def wrap(x):
	return x ^ RANDOM
 
 
a = dict()  # Diccionario para guardar los índices asignados
for _ in range(int(input())):
	nums = list(map(int, input().split()))
	if nums[0] == 0:
		a[wrap(nums[1])] = nums[2]
	elif nums[0] == 1:
		# Imprimir a[k] si está, si no 0
		print(a.get(wrap(nums[1]), 0))

Problemas

Algunos de estos problemas se pueden resolver solo con ordenamiento, aunque conjuntos o mapas pueden facilitar la implementación.

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Sum of Two Values	Fácil	Map	Solución
Bronze	★ Where Am I?	Fácil	Set	Solución
Bronze	Team Tic Tac Toe	Normal	Simulation, Set	Solución
Bronze	Year of the Cow	Normal	Map	Solución
Bronze	★ Don't Be Last!	Normal	Map, Sorting	Solución
Bronze	It's Mooin' Time II	Normal	Map, Set	Solución
Silver	Cities & States	Normal	Map	Solución
CF	Jury Marks	Normal	Set, Prefix Sums	Solución
Bronze	It's Mooin' Time	Difícil	Set, Maps	—
AC	Made Up	Difícil	Map	Solución
CF	Into Blocks	Difícil	Set, Map	Solución

Quiz

C++JavaPython

Pregunta 1/7

¿Cuál es la complejidad temporal en el peor caso de inserciones, eliminaciones y búsquedas en un std::set de tamaño

N

Pregunta 1/7

¿Cuál es la complejidad temporal en el peor caso de inserciones, eliminaciones y búsquedas en un TreeSet de tamaño

N

Pregunta 1/7

¿Cuál es la complejidad temporal en el peor caso de inserciones, eliminaciones y búsquedas en un set de tamaño

N