Post

Plantilla

Plantilla oficial del club Γα=Ω5 para programación competitiva en C++, alineada con el Notebook TRD e ICPC.

Publicado Actualizado
Preview Image
Por Ariel Parra
16 min de lectura
Plantilla

Plantilla Corta

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <bits/stdc++.h>
using namespace std;

void solve() {
    return;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

Tabla de Contenidos:

Plantilla Larga (Oficial de Competencia)

A continuación presentamos la plantilla estándar y completa del club, la cual se encuentra disponible y versionada en el repositorio de GitHub CPC-GALLOS/Plantilla. Está diseñada para maximizar la velocidad de escritura, evitar errores de compilación comunes y proporcionar estructuras de alto rendimiento alineadas con nuestro ICPC Team Reference Document (Notebook TRD):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// _autor_
// link y/o nombre del problema
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // PBDS: estructuras de datos basadas en políticas
#include <ext/pb_ds/tree_policy.hpp>     // Requerido para estadísticas de orden (ordered_set)
using namespace std;
using namespace __gnu_pbds; // PBDS: ordered_set & gp_hash_table

/* TLE Pragmas & Advertencias (descomentar con cuidado):
#pragma GCC optimize("O3,unroll-loops")          // O3 optimiza sin fast-math (que rompe signos en floats: -0.0+0.0=-0)
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // SIMD + operaciones de bits en HW (bmi/lzcnt/popcnt)
*/

using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;

// --- PBDS Policy-Based Data Structures ---
// 1. ordered_set: find_by_order(k) (k-ésimo menor, 0-idx) & order_of_key(x) (cnt < x) en O(log N)
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// Truco para ordered_multiset (duplicados permitidos): usar pair<T, int> con ID único

// 2. gp_hash_table: Tabla hash de direccionamiento abierto 3x-5x más rápida que unordered_map
// gp_hash_table<int, int> fast_map;

#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define gs(n) ((n * (n + 1)) >> 1)
#define pb push_back   // Seguro con llaves {a, b}; evita llamadas a constructores explícitos
#define eb emplace_back // Construcción in-place v.eb(a, b) sin copias temporales
#define F first
#define S second
#define sz(x) (int)(x).size()
#define yn(x) (cout << ((x) ? "YES\n" : "NO\n"))
#define dbg(...) cerr<<"LINE("<<__LINE__<<")->["<<#__VA_ARGS__<<"]: ["<<(__VA_ARGS__)<<"]\n";

// Temporizador de ejecución (para benchmarking local):
// auto start_time = chrono::high_resolution_clock::now();
// auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start_time).count();

void solve() {
    return; // Lógica de solución para cada caso de prueba
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

La plantilla está disponible en el repositorio CPC-GALLOS/Plantilla. ¡Recuerda sugerir tus mejoras a través de un Pull Request!

Explicación y Justificación de la Plantilla Larga

Cada línea de nuestra plantilla ha sido cuidadosamente seleccionada con base en análisis de ensamblador, benchmarks en jueces virtuales como Codeforces y reglamentos del ICPC. A continuación se desglosa el propósito y la mecánica interna de cada componente.

1. La Cabecera y Directivas del Compilador

Inclusión Universal: #include <bits/stdc++.h>

La cabecera <bits/stdc++.h> es un encabezado precompilado de GNU GCC que incluye todas las bibliotecas de la STL de C++ (GNU stdc++.h): <iostream>, <vector>, <algorithm>, <numeric>, <cmath>, <string>, <queue>, <stack>, <set>, <map>, <bitset>, entre otras (Govil, 2022).

<bits/stdc++.h> es un archivo específico de la implementación de GCC y Clang. No forma parte del estándar ISO C++, por lo que en entornos que usan MSVC (Visual Studio tradicional) o Xcode sin GCC puede requerir configuración adicional. En todos los jueces virtuales oficiales (ICPC, Codeforces, AtCoder, CSES) GCC/Clang está soportado y es la opción recomendada.

Su ventaja en competencia es inmensa: ahorra el tiempo de memorizar e incluir manualmente decenas de encabezados y previene errores de compilación por librerías faltantes. El leve incremento en el tiempo de compilación no afecta en absoluto el tiempo de ejecución en el juez virtual.

Policy-Based Data Structures (PBDS)

La plantilla incorpora las bibliotecas de extensiones avanzadas de GCC:

1
2
3

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

1. ordered_set (Árbol Rojo-Negro Aumentado)

La STL tradicional (std::set) no permite saber qué elemento ocupa la posición $k$ ni cuántos elementos son menores a un valor $x$ en tiempo sublineal. Con PBDS definimos:

1
2

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

Esto habilita dos operaciones fundamentales en $O(\log N)$ (adamant, 2014):

  • s.find_by_order(k): Retorna un iterador al $k$-ésimo elemento más pequeño (indexado en base 0). Si $k \ge s.\text{size}()$, retorna s.end().
  • s.order_of_key(x): Retorna la cantidad de elementos estrictamente menores que $x$.

Truco para Multiconjuntos (ordered_multiset): Si necesitas elementos duplicados, no uses less_equal<T> (ya que rompe la función erase), sino un par ordenado ordered_set<pair<T, int>> donde el segundo valor almacena un identificador único incremental.

2. gp_hash_table (Tabla Hash de Alto Rendimiento)

gp_hash_table es una tabla hash de direccionamiento abierto (open addressing with probe sequence) provista por PBDS que suele ser de 3 a 5 veces más rápida que std::unordered_map (la cual utiliza encadenamiento separado / separate chaining).

Directivas #pragma para Vectorización SIMD y TLE

Las directivas #pragma instruyen al optimizador de GCC para generar código vectorial y aprovechar instrucciones del procesador que no siempre se activan por defecto (Nor, 2021; Slotin, 2022):

1
2
3
4

/*
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
*/
  1. optimize("O3,unroll-loops"):
    • O3: Aplica vectorización automática y optimizaciones agresivas sin romper los estándares IEEE 754 de punto flotante. A diferencia de Ofast (que activa -ffast-math y puede producir errores como -0.0 + 0.0 = -0.0 o alteraciones en asociatividad de números flotantes), O3 es seguro para problemas matemáticos y geométricos (Ponml, 2011; Walfridsson, 2021).
    • unroll-loops: Desenrolla bucles de longitud determinable, reduciendo el costo de saltos condicionales (branch overhead) y facilitando el pipeline de instrucciones en la CPU.
  2. target("avx2,bmi,bmi2,lzcnt,popcnt"):
    • avx2: Permite al compilador utilizar registros AVX2 de 256 bits para procesar hasta 8 enteros de 32 bits simultáneamente en una sola instrucción (Intel Guide to Vectorization; Wikipedia AVX).
    • bmi, bmi2, lzcnt, popcnt: Habilita instrucciones de manipulación de bits a nivel de hardware, acelerando operaciones sobre máscaras binarias.

Al usar target("avx2") junto con contenedores o asignadores de memoria de la STL en ciertas versiones antiguas de GCC puede generarse un error de alineación con std::allocator. Por ello, en nuestra plantilla se mantienen comentados para activarlos a discreción cuando un problema intensivo esté al borde del TLE (USACO Vectorization Guide).

2. Tipos de Datos y Aliases (using)

1
2
3
4
5

using ll = long long; 
using ull = unsigned long long; 
using ld = long double;
using pii = pair<int, int>; 
using pll = pair<ll, ll>;

¿Por qué using en lugar de typedef o #define?

  • using es más legible y moderno (estándar C++11 en adelante).
  • A diferencia de typedef, using soporta plantillas con parámetros (template aliases), como vimos con ordered_set (Qualified, 2020).
  • Nunca se debe usar #define ll long long porque es una simple sustitución textual del preprocesador que puede causar errores sintácticos con modificadores (unsigned ll o punteros ll* a, b).

Rangos de Tipos Primitivos (Arquitectura x64)

  • int (32 bits): $[-2.14 \times 10^9, 2.14 \times 10^9]$.
  • ll (long long, 64 bits): $[-9.22 \times 10^{18}, 9.22 \times 10^{18}]$. Obligatorio cuando una suma o producto acumulado supera $2 \times 10^9$ (Microsoft Data Type Ranges).
  • ull (unsigned long long, 64 bits sin signo): $[0, 1.84 \times 10^{19}]$.
  • ld (long double, 80/128 bits): Proporciona entre 18 y 19 dígitos significativos de precisión decimal, crucial en problemas de geometría computacional donde double (15 dígitos) sufre de errores de redondeo.

using namespace std;

En programación competitiva se adopta universalmente para evitar anteponer std:: a cada llamada (cin, cout, vector, sort), ahorrando tiempo y reduciendo la longitud visual del código (Biggs, 2009).

3. Macros Esenciales (#define)

Salto de Línea Rápido: #define endl '\n'

En C++, std::endl no solo inserta el carácter de nueva línea \n, sino que además ejecuta una llamada forzada a flush() en el flujo de salida std::cout (cppreference endl; Langholtz, 2023).

La implementación interna de std::endl en libstdc++ (GNU ostream) demuestra este comportamiento:

1
2
3
4
5

template<typename _CharT, typename _Traits>
inline basic_ostream<_CharT, _Traits>&
endl(basic_ostream<_CharT, _Traits>& __os) {
    return flush(__os.put(__os.widen('\n')));
}

En ensamblador x86-64, una llamada a std::endl genera más de 45 instrucciones incluyendo llamadas a widen, put y flush, mientras que imprimir directamente '\n' requiere únicamente 16 instrucciones y no vacía el búfer del sistema operativo innecesariamente. Con #define endl '\n', podemos seguir usando la sintaxis habitual de cout << x << endl; sin riesgo de TLE.

Macros de Rango y Colecciones: all(x) y rall(x)

1
2

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
  • all(x): Simplifica llamadas a algoritmos de <algorithm> como sort(all(v)), reverse(all(v)) o min_element(all(v)) (Golovanov, 2020).
  • rall(x): Permite ordenar colecciones en orden descendente directo con sort(rall(v)) sin necesidad de pasar greater<T>() como comparador.

Suma de Gauss: #define gs(n) ((n * (n + 1)) >> 1)

Calcula la sumatoria de los primeros $n$ números naturales $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ en tiempo $O(1)$. El operador bitshift derecho >> 1 realiza una división entera entre 2 a nivel de bits.

Tamaño Seguro: #define sz(x) (int)(x).size()

El método .size() de los contenedores STL retorna un tipo sin signo (size_t / unsigned long). Si se realizan operaciones aritméticas como v.size() - 1 cuando el vector está vacío (size() == 0), se produce un subdesbordamiento (underflow) que resulta en $18446744073709551615$, provocando bucles infinitos y fallos de segmentación. Al convertirlo explícitamente a int con sz(x), este peligro queda eliminado.

Salida Booleana Rápida: #define yn(x) (cout << ((x) ? "YES\n" : "NO\n"))

Muchos problemas en Codeforces, AtCoder y concursos ICPC solicitan responder "YES" o "NO". Esta macro evalúa cualquier expresión booleana y emite la respuesta con su salto de línea de forma instantánea.

Macro de Depuración: #define dbg(...)

1

#define dbg(...) cerr<<"LINE("<<__LINE__<<")->["<<#__VA_ARGS__<<"]: ["<<(__VA_ARGS__)<<"]\n";

Permite inspeccionar variables durante la prueba local imprimiendo la línea exacta del código fuente, el nombre de la variable y su valor a través de stderr (std::cerr) (angelbeats, 2020; Gokhale, 2019; Qi et al., Basic Debugging):

1
2

int ans = 42;
dbg(ans); // Salida en consola: LINE(35)->[ans]: [42]

La salida de std::cerr no interfiere con la salida estándar std::cout calificada por los jueces virtuales, pero dejar múltiples llamadas dbg() activas dentro de bucles de $10^6$ iteraciones puede causar TLE.

push_back vs emplace_back y Acceso a Pares

1
2
3
4

#define pb push_back
#define eb emplace_back
#define F first
#define S second
  • F y S: Abreviaciones clásicas para acceder a los miembros de std::pair (p.F y p.S).
  • pb vs eb:
    • emplace_back construye el elemento directamente en la memoria del vector usando perfect forwarding (std::forward), lo cual es muy eficiente al insertar tipos compuestos (cppreference emplace_back; Fertig, 2023; Stone, 2012).
    • En C++ moderno (C++11 en adelante), push_back combinado con inicialización por llaves (brace-initialization v.pb({x, y})) es igualmente óptimo y previene llamadas accidentales a constructores explícitos no deseados (HosseinYousefi, Codeforces #15643).

4. Código Principal (Driver Code) y Fast I/O

1
2
3
4
5
6
7
8
9
10
11
12

void solve() {
    return; // Lógica del problema
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

Mecánica de Fast I/O: cin.tie(0)->sync_with_stdio(0);

Anteriormente se solía escribir en dos sentencias separadas: ios::sync_with_stdio(0); cin.tie(0);. La sintaxis moderna y compacta cin.tie(0)->sync_with_stdio(0); (popularizada en referencias contemporáneas de programación competitiva como Structdex) aprovecha dos propiedades fundamentales del estándar de C++:

  1. cin.tie(0) desacopla los flujos y retorna el puntero previo: En C++, std::cin está enlazado (tied) por defecto a std::cout, lo que significa que antes de cada operación de lectura cin vacía forzosamente el búfer de cout (Gorbachev, 2021; Qi & Chen, Fast I/O). Al llamar a basic_ios::tie(0) (o nullptr), se rompe este enlace para permitir lecturas continuas a máxima velocidad. Crucialmente, tie() retorna el puntero al flujo previamente enlazado (std::ostream*), el cual corresponde a &std::cout.
  2. Invocación de métodos estáticos mediante ->: La función sync_with_stdio es un método estático (static bool sync_with_stdio(bool sync = true);) definido en la clase base std::ios_base (de la cual hereda std::ostream). Según el estándar ISO C++, llamar a un método estático mediante sintaxis de miembro/puntero (p->metodo_estatico()) es completamente válido: el compilador evalúa la expresión izquierda (cin.tie(0) realiza el desacople) y despacha la llamada estática sobre la clase.
  3. Desactivación de sincronización con stdio: sync_with_stdio(0) desactiva la sincronización obligatoria entre los flujos estándar de C (stdio) y los de C++ (iostream), permitiendo que C++ opere con búferes internos independientes mucho más grandes y eficientes (cplusplus sync_with_stdio; yak_ex, 2011).

Tras desactivar la sincronización, no se deben mezclar funciones de C (printf, scanf, getchar) con std::cin y std::cout en el mismo programa, ya que la independencia de búferes puede desordenar entradas y salidas.

Estructura Modular: void solve() y Casos de Prueba (while (tc--))

En lugar de concentrar toda la solución dentro de la función main, nuestra plantilla delega cada caso de prueba a la función void solve():

  1. Facilita la salida temprana: Permite usar return; en cualquier momento dentro de solve() al detectar un caso base o responder una consulta, sin detener la ejecución de los siguientes casos de prueba.
  2. Ciclo while (tc--): En ensamblador, un bucle decremental comparando contra 0 genera menos instrucciones de salto condicional que un bucle for (int i = 0; i < tc; i++).
  3. Control de Estado: En problemas multi-testcase (cin >> tc), es fundamental recordar reiniciar todas las variables globales y estructuras de datos (vector.clear(), memset) al inicio de cada llamada a solve().

Redirección de Archivos: freopen

Para competencias presenciales o pruebas locales con archivos de prueba grandes, basta con descomentar:

1
2

freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);

Todas las lecturas de cin provendrán del archivo in.txt y las salidas se escribirán automáticamente en out.txt.

5. Configuración en VS Code

Para utilizar esta plantilla de forma automática al abrir cualquier problema, recomendamos la extensión oficial Competitive Programming Helper (CPH) para Visual Studio Code:

  1. Abre los ajustes de VS Code (Ctrl + , / Cmd + ,).
  2. Busca cph.general.defaultLanguageTemplateFileLocation.
  3. Selecciona la ruta absoluta hacia tu archivo Plantilla.cpp.

Configuración de plantilla en CPH

Para más detalles sobre cómo armar tu entorno completo de desarrollo con GCC, VS Code y snippets, consulta nuestro artículo sobre Entorno de Desarrollo.

Referencias

Club
recomendaciones C++
Esta publicación tiene la licencia CC BY 4.0 del autor.