Post

Plantilla

Plantilla del club Γα=Ω5 para su uso en la programación competitiva en C++

Publicado Actualizado
Por Ariel Parra
21 min de lectura
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

// _autor_
// link y/o nombre del programa
//#pragma GCC optimize("Ofast,unroll-loops")//-0.0+0.0=-0  
//#pragma GCC target("avx2") // STL cointaner = std::allocator err
#include <bits/stdc++.h>

using ull = unsigned long long;
using ll = long long;
using namespace std;
#define endl '\n'
#define all(x) (x).begin(), (x).end() 
#define yn(x) (cout << ((x) ? "YES" : "NO"))
#define dbg(...) cerr<<"LINE("<<__LINE__<<")->["<<#__VA_ARGS__<<"]: ["<<(__VA_ARGS__)<<"]\n";   
#define pb push_back 
#define F first
#define S second

int main(){
ios::sync_with_stdio(0);cin.tie(0);
//freopen("in.txt", "r", stdin);
    int tc=1;
    //cin>>tc;
    int n;
    while(tc--){
        cin>>n;
        for(int i=0;i<n;++i){
            //code
        }
    }
return 0;
}

Tabla de contenidos

Explicación y justificación de la plantilla

La cabecera (header)

Directivas #pragma para la vectorización

Las directivas #pragma no son estándar y solo funcionan en los compiladores de GNU como gcc y g++. Es muy común que arroje un error al querer compilar en Xcode, ya que este usa el compilador Clang, al igual que en Visual Studio que usa el compilador MSVC.

Estos pueden solucionar ciertos TLE como en los problemas dentro de este link, pero al usar el pragma GCC target("avx2") junto con containers del STL o iteradores o cualquier función de la STL que use internamente std::allocator() soltara un error, asi que descomentar los pragmas a discreción

La vectorización es el desarrollo de un bucle combinado con la generación de instrucciones SIMD (Single Instruction, Multiple Data) empaquetadas por parte del compilador para los procesadores con arquitectura x86.

Los juzgados virtuales son los que compilan nuestros códigos, por lo que no podemos aplicar parámetros al compilador directamente como lo haríamos en nuestra terminal, por ejemplo en este caso se aplica la optimización O2 (la optimización por defecto) al compilador g++: g++ -O2 code.cpp. Y no habría problema en no poder editar los parámetros de compilación si no se haya visto ya en múltiples ocasiones que no usarlos puede ocasionar un Time limit exceeded, como en el problema 855F Nagini, donde paso que cuando no se usaron los pragmas lanzo un TLE y cuando si se usaron pragmas se pudo reducir el tiempo hasta en un 61.4%.

En nuestra plantilla incluimos el #pragma optimize("Ofast,unroll-loops"), que seria similar a ejecutar g++ -Ofast -funroll-loops code.cpp

  • El parámetro ‘Ofast’ aplica todas las optimizaciones agresivas de ‘O3’ junto con otras optimizaciones que rompen algunos de los estándares de C++, ya que también incluye el parámetro -ffast-math el cual trae problemas con números de punto flotante, por lo que se recomienda cambiar a ‘O3’ para problemas geométricos o que usen números decimales.

  • El parámetro ‘fast-math’ asume que la aritmética de punto flotante es asociativa por lo que puede dar resultados , también redondea números ‘denormals’ a 0.0 ya que el manejarlos es costoso para el procesador y por ultimo puede dar errores de signo como lo es en el caso de las sumas con signo de cero. Una manera de mitigar ligeramente los efectos es usar double en lugar de float, pero aun así existirán errores.

    Esto se puede ver reflejado en este fragmento de código:

    1
2
3
4

      float a = 1.0f, b = 1e10f, c = -1e10f;
  float sum = a + (b + c);        // difiere de: (a + b) + c resultando en 1 envés de 0
  float denormal = 1e-45f - 0.0f; // se redondea a 0.0 en lugar de 1.42857e+09 
  float zero = -0.0f + 0.0f;      // Resulta en -0.0 en lugar de 0.0

  • El parámetro ‘unroll-loops’ permite un desarrollo agresivo del bucle convirtiendo los bucles con longitud determinable en múltiples instrucciones, lo que reduce el número de ramas (branches) y optimiza el cálculo en paralelo, pero esto aumenta el tamaño del código y puede provocar errores en la caché de instrucciones.

    Por ejemplo, este bucle:

    1
2
3

      for (int i = 0; i < 5; ++i){
      std::cout << i ;
  }

    se podría convertir bajo el parámetro ‘unroll-loops’ en algo similar a esto:

    1
2
3
4
5
6

      int i = 0;
  if (i < 5) { std::cout << i; ++i; }
  if (i < 5) { std::cout << i; ++i; }
  if (i < 5) { std::cout << i; ++i; }
  if (i < 5) { std::cout << i; ++i; }
  if (i < 5) { std::cout << i; ++i; }

En nuestra plantilla también incluimos #pragma GCC target("avx2"), esto permite la vectorización y optimización de operaciones en vectores al decirle al compilador que genere el código utilizando estas instrucciones a procesadores que soportan el conjunto de instrucciones AVX2.

Las instrucciones regulares (sin AVX) son ejecutadas por el procesador una a la vez, mientras que las instrucciones AVX usan registros especiales capaces de contener más bits que un registro normal. Por ejemplo, hay procesadores que admiten AVX-256pueden realizar operaciones (como cargar, almacenar, sumar, etc.) en 256 bits que pueden contener 8 enteros de 32 bits, 4 números de punto flotante de 64 bits, o 2 enteros de 64 bits simultáneamente. Esto básicamente es un tipo de paralelismo a nivel de instrucción (SIMD), lo que significa que puedes realizar operaciones sobre múltiples datos alineados en paralelo.

Esto llega a ser muy útil, por ejemplo, cuando se trabaja con matrices, los bucles pueden tomar pasos más grandes y ejecutar operaciones en múltiples elementos simultáneamente, lo que puede resultar en una aceleración de hasta 2, 4 o incluso 8 veces más en comparación con el código sin estas optimizaciones.

Directiva #include <bits/stdc++.h>

La librería <bits/stdc++.h> no es estándar y solo funciona en los compiladores de GNU como gcc y g++. Es muy común que arroje un error al querer compilar en Xcode, ya que este usa el compilador Clang, al igual que en Visual Studio que usa el compilador MSVC.

En nuestra plantilla usamos #include<bits/stdc++.h> ya que esta librería incluye todas las librerías de la STL que podríamos utilizar en nuestros algoritmos como lo son: <algorithm>, <bitset>, <iostream>, <iterator>, <limits>, <map>, <queue>, <set>, <stack>, <vector>, entre otras librerías.

La única desventaja de incluir esta librería aparte de no ser estándar, es que incrementa el tiempo de compilación, pero como el tiempo de compilación no afecta al resultado del juez virtual, entonces el incluirla nos ahorra el tiempo que tardaríamos en memorizar e incluir cada librería a mano.

Definiciones globales (Global definitions)

Directiva using

using es una directiva usada para definir apodos/sinónimos/alias para un tipo de dato y a diferencia de la directiva typedef, using permite el uso en y de containers (estructuras de datos) de la librería estándar (STL).

Algunos ejemplos de usos comunes seria para un tipo de dato entero matricial: using imat = std::vector<std::vector<int>>; o para ahorrar los parámetros del tipo de dato de un container, por ejemplo using llvec = std::vector<ll>;, using iip = std::pair<int,int>;, using icp = std::pair<int,char>;, etc.

En nuestro caso uno de los tipos de datos más usados es el tipo de dato long long y unsigned long long, debido a que tienen capacidad de 8 bytes en procesadores de 64 bits.

  • long long: Tiene un rango que va desde -9,223,372,036,854,775,808 hasta 9,223,372,036,854,775,807
  • unsigned long long: Tiene un rango que va desde 0 hasta 18,446,744,073,709,551,615

Mucho cuidado de no confundir long long con long, ya que el tipo de dato long es un sinónimo de int teniendo ambas una capacidad de 4 bytes.

using namespace std

En programación competitiva, utilizamos using namespace std; para evitar escribir std:: antes de cada función o contendedor de la librería estándar (STL) repetidamente y ahorrar tiempo. Sin embargo, fuera de la programación competitiva, usar using namespace std; es una muy mala práctica. En un proyecto real, donde se importan varias librerías, pueden surgir conflictos de nombres.

Por ejemplo, considera que tu proyecto utiliza las funciones std::static_cast y std::bind, pero también incorpora múltiples funciones de la librería Boost, como boost::lexical_cast y boost::bind. No habrá problemas si se usa static_cast o lexical_cast sin los prefijos de las librerías, pero si se quisiera usar la función bind, el proyecto puede compilar correctamente pero no funcionaria como se esperaba, ya que todas las referencias a la función bind se asumirán como std::bind en lugar de boost::bind.

La alternativa a usar using namespace std; es emplear declaraciones específicas para los elementos que se necesiten, como using std::cin;, using std::cout;, using std::cerr;, etc.

Directivas #define

Las directivas #define en C y C++ funcionan de manera similar a las macros y la directiva equ en ensamblador, ya que ambas permiten la sustitución directa de código cuando son referenciadas.

Por ejemplo en C:

1
2

#define TAM_MAX 50
#define sum(a, b) ((a) + (b))

En el ensamblador (NASM) seria:

1
2
3
4

TAM_MAX equ 50
%macro sum 2
    %1 + %2
%endmacro

#define endl ‘\n’

std::endl es una de las maneras más comunes de insertar un salto de línea en C++, pero no solo inserta una nueva línea \n sino que también hace un ‘flush’ al flujo de salida estándar stdout, en pocas palabras es similar a ejecutar la función std::ostream::.put('\n') o std::basic_ostream::put(std::basic_ios::widen('\n')) y luego hacer std::basic_ostream::flush.

Por esto en nuestra plantilla definimos cualquier llamada a endl hacia al carácter \n, para que podamos seguir usando esa función sin miedo a ralentizar el programa.

Pero aun así en muchas implementaciones de C++, escribir \n provoca un ‘flush’ de todos modos, a menos que se haya ejecutado std::ios::sync_with_stdio(false) anteriormente como es el caso de nuestra plantilla, por lo que usar directamente std::endl es malo ya que en el caso del compilador GCC, este ejecuta tres pasos antes de ejecutar la función:

  1. Conversión del Carácter: __os.widen('\n'): Convierte el carácter \n al tipo de carácter ‘wide’ según la configuración regional del flujo obtenida por el parámetro _Traits.
  2. Inserción del Carácter: __os.put(__os.widen('\n')): Inserta el carácter convertido en el flujo de salida. Esta operación agrega el carácter \n al búfer del flujo a través de la función put
  3. Flush del búfer : flush(__os.put(__os.widen('\n'))) llama a flush(), que a su vez llama a __os.flush() para asegurar que todos los datos en el búfer del flujo se escriban inmediatamente en la salida estándar (stdout).

Dado estos pasos, la función std::endl se implementa así en el compilador GCC:

1
2
3
4

  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 la función std::endl se veria de esta manera:

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

doEndl():
        push    rbx
        mov     edx, 12
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:std::cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        mov     rax, QWORD PTR std::cout[rip]
        mov     rax, QWORD PTR [rax-24]
        mov     rbx, QWORD PTR std::cout[rax+240]
        test    rbx, rbx
        je      .L10
        cmp     BYTE PTR [rbx+56], 0
        je      .L5
        movsx   esi, BYTE PTR [rbx+67]
.L6:
        mov     edi, OFFSET FLAT:std::cout
        call    std::basic_ostream<char, std::char_traits<char> >::put(char)
        pop     rbx
        mov     rdi, rax
        jmp     std::basic_ostream<char, std::char_traits<char> >::flush()
.L5:
        mov     rdi, rbx
        call    std::ctype<char>::_M_widen_init() const
        mov     rax, QWORD PTR [rbx]
        mov     esi, 10
        mov     rax, QWORD PTR [rax+48]
        cmp     rax, OFFSET FLAT:_ZNKSt5ctypeIcE8do_widenEc
        je      .L6
        mov     rdi, rbx
        call    rax
        movsx   esi, al
        jmp     .L6
.L10:
        call    std::__throw_bad_cast()
_GLOBAL__sub_I_doEndl():
        sub     rsp, 8
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        add     rsp, 8
        jmp     __cxa_atexit

A diferencia de solo imprimir el caracter \n:

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

doNewline():
        mov     edx, 13
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
_GLOBAL__sub_I_doNewline():
        sub     rsp, 8
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        add     rsp, 8
        jmp     __cxa_atexit

donde solo imprimir \n resulta en 16 líneas de ensamblador comparadas con las 45 líneas necesarias para std::endl, más líneas en ensamblador no necesariamente significa peor rendimiento, el problema es que como estas afectan directamente al búfer de salida, aquí si afecta la cantidad de líneas.

Macros

#define all(x)

Esta macro simplifica el uso de rangos en contenedores STL. En lugar de escribir x.begin(), x.end(), puedes usar all(x) para pasar el rango de iteradores a funciones como sort.

1
2
3

vector<int> v{3,4,1,2};
sort( v.begin(),v.end() );
sort( all(v) );
#define yn(x)

Esta macro imprime “YES” si x es verdadero y “NO” si x es falso, proporcionando una forma rápida de mostrar resultados booleanos en la salida estándar.

1
2
3
4

bool flag = true;
yn(flag);  // Imprime: YES
flag = !flag;
yn(flag); // Imprime: NO
#define dbg(…)

La macro dbg() nos permite ejecutar de una manera simple nuestros códigos, solamente rodeamos alguna variable o función que devuelva valores y nos dirá en que línea esta, cual variable y su valor.

1
2
3
4
5
6

int i=3;
while(--i){
    dbg(i);/* imprime: `LINE(3)->[i]: [2]` y `LINE(3)->[i]: [1]` */
}
int j = i;
dbg(j);// imprime: `LINE(6)->[j]: [0]`

dejar múltiples dbg() incluidos puede causar un TLE al subir el problema.

defines para Containers

los defines restantes son usados para optimizar la escritura de los containers (estrucutras de datos) de la STL, usamos Fy S para acceder al primer first o segundo second elemento de un pair o map, y también usamos el atajo pb para ahorrarnos tiempo al escribir push_back.

Varias plantillas incluyen eb para emplace_back, esta funciona de manera similar a push_back, pero la principal diferencia tiene que ver con constructores implícitos contra constructores explícitos.

  • emplace_back construye el nuevo elemento en su lugar utilizando los argumentos proporcionados como argumentos para su constructor.
1
2
3
4
5
6
7
8
9

void emplace_back(Args&&... args) {
    if (size == capacity) {
        // redimension del vector
        reserve(capacity == 0 ? 1 : 2 * capacity);
    }
    // Coloca el nuevo elemento en el lugar apropiado usando `new`
    new(&data[size]) T(std::forward<Args>(args)...);
    ++size;
}
  • push_back construye un elemento copia en un espacio auxiliar, para después moverlo al final del container.
1
2
3
4
5
6
7
8
9

void push_back(const T& value) {
    if (size == capacity) {
        // redimension del vector
        reserve(capacity == 0 ? 1 : 2 * capacity);
    }
    // Copia el valor en el lugar apropiado
    data[size] = value;
    ++size;
}

Pero hay que tener cuidado, ya que se ha visto en varias ocasiones que usar emplace_back produce errores como en este post, o en un ejemplo más simple:

1
2
3
4

std::vector<std::unique_ptr<T>> v;
T a;
v.emplace_back(std::addressof(a)); // compila
v.push_back(std::addressof(a)); // no compila

Esto sucede ya que std::unique_ptr<T> tiene un constructor explícito de T *. Debido a que emplace_back puede usar constructores explícitos, pasar un puntero que no es propietario si compilara. Sin embargo, cuando v sale del alcance (scope), el destructor intentará eliminar ese puntero, que no fue asignado por new porque es solo un objeto de la pila (stack). Esto lleva a comportamientos indefinidos.

En conclusión recomendamos usar push_back para evitar errores en la programación competitiva, pero si se quisiera usar ambas funciones recomendamos usar push_back solamente cuando quieras mover un objeto ya existente hacia un container y usar emplace_back cuando los elementos en si son containers ya que esto en sí, si será más rápido.

Algunos ejemplos donde emplace_back es más rápido:

1
2
3
4

vector<pair<int,int>> vpii;
vpii.push_back(make_pair(1, 2)); 
vpii.emplace_back(make_pair(1, 2)); // misma velocidad que `push_back`
vpii.emplace_back(1, 2); // misma velocidad pero sintaxis simplificada

1
2
3
4
5

vector<vector<int>> imat;
imat.push_back(vector<int>{1, 2, 3}); /* usa el constructor vector<int> 
                                         y luego lo mueve al container externo*/
imat.emplace_back(vector<int>{1, 2, 3}); // realiza lo mismo
imat.emplace_back(initializer_list<int>{1, 2, 3}); // más rápido, mueve los datos al constructor

Código principal (Driver code)

E/S rápida (Fast I/O)

La función ios::sync_with_stdio(0) desactiva la sincronización entre los flujos estándar de C y C++. De forma predeterminada, todos los flujos estándar están sincronizados, lo que en la práctica le permite combinar E/S con estilos de C y C++ y obtener resultados predecibles. Si se desactiva la sincronización, entonces los flujos de C++ pueden tener sus propios buffers independientes, lo que hace más eficiente la entrada y salida de datos con std::cin y std::cout.

En múltiples plantillas esta incluido el uso de std::ios_base::sync_with_stdio(false) en nuestro caso al usar using namespace std; ahorramos la parte de escribir std::, también en lugar de false solo colocamos un 0 que tendrán el mismo valor, por ultimo usamos ios solamente en lugar de ios_base para ahorrarnos el escribir esos 5 caracteres extra, ya que basic_ios hereda de ios_base e ios es un alias de basic_io

Recordar que esta función elimina la compatibilidad de interfaces entre C (<stdio.h>) y C++ (<iostream>), por lo que se recomienda evitar el uso simultáneo de funciones printf y scanf de C junto con las de C++ std::cin y std::cout.

En nuestra plantilla también incluimos, esto le dice a std::cin que no debe esperar a que se vacíe el búfer de salida estándar (stdout) dado por std::cout, antes de poder realizar sus operaciones. Esto se debe a que por defecto std::cin esta atado a std::cout y debe esperar a que se vacíe dicho búfer.

Cuidado al usar esta función al debugear o usarla en códigos ajenos a la programación competitiva ya que cambia la secuencia lógica en la que se muestran los std::cout

En varios códigos también se puede encontrar el uso de cout.tie(NULL), y esto literalmente no hace nada ya que std::cout ya está atado a NULL por defecto.

También en nuestra plantilla incluimos //freopen("in.txt", "r", stdin");, que es útil para competencias reales donde no tenemos acceso para copiar y pegar múltiples casos en nuestros programas. Podemos descomentar esta línea y todos los std::cin en nuestro programa serán leídos desde un archivo llamado in.txt en lugar de la terminal.

while test cases

La variable tc significa en este caso ‘test cases’ (casos base), y esta variable se usa cuando un problema te pide repetir el mismo algoritmo múltiples veces.

al no afectar al tamaño de entrada, esta variable no afecta a la complejidad de tiempo del código

1
2
3
4
5

int tc = 10;
// Decrementa tc y repite el bucle si tc no es cero
while(tc--) { 
  // código a ejecutar: cin >> n; ...  
}

1
2
3
4

mov ecx, 10
while:
    ; código a ejecutar
    loop while ; Decrementa ecx y salta a "while" si ecx no es cero

esto es un poco más eficiente que:

1
2
3

for (int tc = 10; tc > 0 ; tc--) {
  // código a ejecutar   
}

1
2
3
4
5
6
7

for_loop:
    cmp ecx, 0         ; Compara ecx con 0
    jle end_loop       ; Si ecx <= 0, salta al final del bucle
    ; código a ejecutar
    dec ecx            ; Decrementa ecx (equivalente a tc--)
    jmp for_loop       ; Salta de nuevo al inicio del bucle
end_loop:

quizá no parezca mucho pero esto llega a optimizar el uso de líneas de ensamblador en un 75%

++i en lugar de i++

La diferencia entre el operador prefijo ++i y el operador postfijo i++ radica en el momento en que la variable es incrementada.

  • Para el operador prefijo ++i, la variable se incrementa antes de que se use:
1
2
3
4

Foo& Foo::operator++() {
  this->data += 1;
  return *this;
}
  • Para el operador postfijo i++, la variable se usa y luego se incrementa:
1
2
3
4
5
6

Foo Foo::operator++(int ignored_value) { 
  Foo tmp(*this);   /* la variable "tmp" no puede 
                    ser optimizada por el compilador */
  ++(*this);
  return tmp;
}

Esto se ve más claro en los siguientes ejemplos:

1
2
3
4
5

int i,j,k,l; i = j = k = l = 0;
std::cout << (i=i+1); // mostrara 1
std::cout << (j+=1);  // mostrara 1
std::cout << (++k);   // mostrara 1
std::cout << (l++);   // mostrara 0

1
2
3
4
5
6
7

int i = 10, j = 10;
while (--j) { // se ejecutara 9 veces
  // código a ejecutar 
}
while (j--) { // se ejecutara 10 veces
 // código a ejecutar 
}

En la plantilla tenemos for(int i=0;i<n;++i) en lugar de for(int i=0;i<n;i++) ya que aunque el for ejecute el incremento al final en ambos casos, usar el operador prefijo optimiza un poco la complejidad en el espacio, ahorrándonos la creación de un objeto temporal por cada iteración de los ciclos.

Referencias

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

Diseñado con ❤️ por Ariel Parra.

© CPC-GALLOS. Algunos derechos reservados.

Hecho con Jekyll usando el tema Chirpy