A implementação utiliza uma estrutura de trie para armazenar as permutações. O código abaixo foi refatorado com nomes de variáveis e lógica alterados.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAX_PERM = 1e6 + 10;
int perm_input[MAX_PERM][11];
int trie[MAX_PERM][11];
int node_counter;

void resolver() {
    int quantidade, tamanho;
    cin >> quantidade >> tamanho;
    
    for (int idx = 1; idx <= quantidade; idx++) {
        for (int elem = 1; elem <= tamanho; elem++) 
            cin >> perm_input[idx][elem];
        
        vector<int> posicao(tamanho + 1);
        for (int elem = 1; elem <= tamanho; elem++) 
            posicao[perm_input[idx][elem]] = elem;
        
        int no_atual = 0;
        for (int valor = 1; valor <= tamanho; valor++) {
            int caractere = posicao[valor];
            if (!trie[no_atual][caractere]) 
                trie[no_atual][caractere] = ++node_counter;
            no_atual = trie[no_atual][caractere];
        }
    }
    
    for (int idx = 1; idx <= quantidade; idx++) {
        int no_atual = 0;
        int comprimento = tamanho;
        for (int pos = 1; pos <= tamanho; pos++) {
            int caractere = perm_input[idx][pos];
            if (!trie[no_atual][caractere]) {
                comprimento = pos - 1;
                break;
            }
            no_atual = trie[no_atual][caractere];
        }
        cout << comprimento << " ";
    }
    cout << endl;
    
    for (int i = 0; i <= node_counter; i++) 
        memset(trie[i], 0, sizeof trie[i]);
    node_counter = 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos;
    cin >> casos;
    while (casos--) resolver();
    return 0;
}

Problema 1810D: Escalando a Árvore

Esta solução calcula limites de altura usando tipos de dados de 64 bits. A estrutura principle do algoritmo foi mantida, mas os nomes e partes da lógica foram reescritos.

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;

void resolver() {
    ll consultas;
    cin >> consultas;
    ll lim_inferior = -1, lim_superior = -1;
    
    while (consultas--) {
        ll tipo;
        cin >> tipo;
        
        if (tipo == 1) {
            ll a, b, n;
            cin >> a >> b >> n;
            ll altura_min, altura_max;
            
            if (n >= 2) {
                altura_max = (a - b) * (n - 1) + a;
                altura_min = (a - b) * (n - 2) + a + 1;
            } else if (n == 1) {
                altura_min = 1;
                altura_max = a;
            }
            
            if (lim_inferior == -1 && lim_superior == -1) {
                lim_inferior = altura_min;
                lim_superior = altura_max;
                cout << 1 << " ";
            } else {
                if (altura_max < lim_inferior || altura_min > lim_superior) 
                    cout << 0 << " ";
                else {
                    lim_inferior = max(lim_inferior, altura_min);
                    lim_superior = min(lim_superior, altura_max);
                    cout << 1 << " ";
                }
            }
        } else {
            ll a, b;
            cin >> a >> b;
            
            if (lim_inferior == -1 && lim_superior == -1) {
                cout << -1 << " ";
                continue;
            }
            
            ll passos_min, passos_max;
            
            if (lim_inferior <= a) passos_min = 1;
            else {
                passos_min = (lim_inferior - a) / (a - b) + 1;
                while ((a - b) * (passos_min - 1) + a < lim_inferior) passos_min++;
            }
            
            if (lim_superior <= a) passos_max = 1;
            else {
                passos_max = (lim_superior - a) / (a - b) + 1;
                while ((a - b) * (passos_max - 1) + a < lim_superior) passos_max++;
            }
            
            if (passos_min == passos_max) cout << passos_min << " ";
            else cout << -1 << " ";
        }
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos;
    cin >> casos;
    while (casos--) resolver();
    return 0;
}

Problema: Partidas com Diferença Zero

A abordagem utiliza programação dinâmica para maximizar a contagem de valores com diferença zero. A lógica de transição de estado foi modificada.

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;

const int MAX_VAL = 1e5 + 10;
int frequencia[MAX_VAL];
ll pd[MAX_VAL];

void resolver() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
        int valor;
        cin >> valor;
        frequencia[valor]++;
    }
    
    if (k == 0) {
        ll resposta = 0;
        for (int i = 0; i < MAX_VAL; i++)
            if (frequencia[i]) resposta++;
        cout << resposta << endl;
        return;
    }
    
    ll total = 0;
    for (int base = 0; base < k; base++) {
        pd[base] = frequencia[base];
        pd[base + k] = max(frequencia[base + k], frequencia[base]);
        ll max_acumulado = 0;
        
        for (int elem = base + 2 * k; elem < MAX_VAL; elem += k) {
            pd[elem] = max(pd[elem - k], pd[elem - 2 * k] + frequencia[elem]);
            max_acumulado = max(pd[elem], max_acumulado);
        }
        total += max_acumulado;
    }
    cout << total << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos = 1;
    while (casos--) resolver();
    return 0;
}

Problema F: Formas em L

A verificação de formas em L é feita examinando vizinhos em uma grade. As funções de validação foram simplificadas e reescritas.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAX_DIM = 110;
char grade[MAX_DIM][MAX_DIM];
bool visitado[MAX_DIM][MAX_DIM];
const int vizinhos[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}};

bool verificar_forma_L(int x, int y) {
    int total_estrelas = 0;
    bool formato_valido = false;
    
    for (int i = x-1; i <= x+1; i++) {
        for (int j = y-1; j <= y+1; j++) {
            if (grade[i][j] == '*') {
                total_estrelas++;
                int vizinhos_estrela = 0;
                for (int d = 0; d < 4; d++) {
                    int nx = i + vizinhos[d][0];
                    int ny = j + vizinhos[d][1];
                    if (nx >= x-1 && nx <= x+1 && ny >= y-1 && ny <= y+1 && grade[nx][ny] == '*') 
                        vizinhos_estrela++;
                }
                if (vizinhos_estrela == 2) formato_valido = true;
            }
        }
    }
    return (total_estrelas == 3 && formato_valido);
}

bool verificar_grupo(int x, int y) {
    int contador = 0;
    for (int i = x-1; i <= x+1; i++)
        for (int j = y-1; j <= y+1; j++)
            if (grade[i][j] == '*') contador++;
    return contador == 3;
}

void resolver() {
    memset(visitado, 0, sizeof visitado);
    memset(grade, 0, sizeof grade);
    int linhas, colunas;
    cin >> linhas >> colunas;
    
    for (int i = 1; i <= linhas; i++)
        for (int j = 1; j <= colunas; j++)
            cin >> grade[i][j];
    
    for (int i = 1; i <= linhas; i++) {
        for (int j = 1; j <= colunas; j++) {
            if (grade[i][j] == '*' && !visitado[i][j]) {
                if (!verificar_forma_L(i, j)) {
                    cout << "NO" << endl;
                    return;
                }
            }
        }
    }
    
    for (int i = 1; i <= linhas; i++) {
        for (int j = 1; j <= colunas; j++) {
            if (grade[i][j] == '*') {
                if (!verificar_grupo(i, j)) {
                    cout << "NO" << endl;
                    return;
                }
            }
        }
    }
    
    cout << "YES" << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos;
    cin >> casos;
    while (casos--) resolver();
    return 0;
}