Sea $A$ la secuecnia original de tamaño $2n$. Definimos $a_x = \{i, j\}$ si y solo si $A_i = A_j = x$ con $i < j$. En particular, $a_0 = \{1, 1\}$.

En otras palabras, $a_i$ representa las posiciones de ambas personas al recoger una piedra de tamaño $i$, con $a_{i,0} < a_{i,1}$.

La respuesta total es simplemente la suma de los desplazamientos absolutos entre recolecciones consecutivas:

$$\text{resp} = \sum_{i=1}^{n} |a_{i,0} - a_{i-1,0}| + |a_{i,1} - a_{i-1,1}|$$

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

int main() {
    int total;
    scanf("%d", &total);
    pair<int,int> pos[100005];
    pos[0] = {1, 1};
    for (int idx = 1; idx <= 2 * total; idx++) {
        int val;
        scanf("%d", &val);
        if (pos[val].first == 0)
            pos[val].first = idx;
        else
            pos[val].second = idx;
    }
    long long dist = 0;
    for (int s = 1; s <= total; s++) {
        dist += abs(pos[s].first - pos[s-1].first);
        dist += abs(pos[s].second - pos[s-1].second);
    }
    printf("%lld\n", dist);
    return 0;
}

Problema B: Fusión de pociones

Dos pociones de volumen $2^i$ se pueden combinar en una de volumen $2^{i+1}$. Se procesan las pociones desde el volumen más pequeño hacia el mayor, fusionando tantos pares como sea posible en cada nivel.

La cantidad de botellas restantes al final del proceso de fusión corresponde a la respuesta.

#include <cstdio>
const int LIMIT = 2000010;
int cnt[LIMIT];
int main() {
    int num;
    scanf("%d", &num);
    for (int i = 0; i < num; i++) {
        int sz;
        scanf("%d", &sz);
        cnt[sz]++;
    }
    int bottles = 0;
    for (int lvl = 0; lvl < LIMIT; lvl++) {
        bottles += cnt[lvl] & 1;
        cnt[lvl + 1] += cnt[lvl] >> 1;
    }
    printf("%d\n", bottles);
    return 0;
}

Problema C: Agrupación de secuencias consecutivas

Si existe una agrupación válida, se puede determinar el esquema de agrupación para el elemento mínimo $x$ como el intervalo $[x, x+m-1]$. Al almacenar las frecuencias en un mapa, el problema se reduce a repetir $\frac{n}{m}$ veces lo siguiente:

1. Encontrar el mínimo $x$ en el mapa.
2. Verificar que todos los valores en $[x, x+m-1]$ tengan frecuencia positiva.
3. Decrementar las frecuencias de dichos valores, eliminando los que lleguen a cero.

Usando std::map directamente, la complejidad temporal es $O(n \log w)$, donde $w$ es el rango de valores.

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

int main() {
    int casos;
    scanf("%d", &casos);
    while (casos--) {
        int n, m;
        scanf("%d %d", &n, &m);
        map<int, int> bucket;
        for (int i = 0; i < n; i++) {
            int val;
            scanf("%d", &val);
            bucket[val]++;
        }
        if (n % m != 0) {
            printf("false\n");
            continue;
        }
        bool valid = true;
        int need = n / m;
        while (need-- && valid) {
            int lo = bucket.begin()->first;
            for (int cur = lo; cur < lo + m; cur++) {
                auto it = bucket.find(cur);
                if (it == bucket.end()) {
                    valid = false;
                    break;
                }
                it->second--;
                if (it->second == 0)
                    bucket.erase(it);
            }
        }
        printf(valid ? "true\n" : "false\n");
    }
    return 0;
}

Problema D: Ecuaciones con opeardores binarios

Se tienen las ecuaciones $x \mid y = A$ y $x + y = B$. Si el sistema tiene solución, entonces $x = A$ y $y = B - A$ es una solución válida.

Justificación: Sea $X_i$ el bit $i$-ésimo de $X$. Entonces $A_i = 1$ si y solo si $x_i = 1$ ó $y_i = 1$. Se pueden mover todos los bits encendidos de $y$ hacia $x$, resultando en $x = A$ y $y = B - A$.

Por lo tanto, el sistema tiene solución si y solo si $A \mid (B - A) = A$, lo que equivale a verificar que $B - A$ no active ningún bit que no esté en $A$.

#include <cstdio>
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long A, B;
        scanf("%lld %lld", &A, &B);
        long long y_val = B - A;
        printf((A | y_val) == A ? "Possible\n" : "Impossible\n");
    }
    return 0;
}