333 Permutación (Editorial)

Consideremos la construcción a través de módulos, solo tenemos 3 opciones \{0,1,2\}, notemos un patrón válido estable, antes de eso debemos identificar los tripletes válidos

y para evitar demasiados casos, consideremos un segmento largo repetido que sea válido, podemos considerar un segmento de [2,2,0,0,1,1], notemos que en el peor de los casos solo quedarán 5 elementos para distribuir correctamente. Aquí está el segmento fijo:

Ahora consideremos los casos restantes:

• n \bmod 6=0 : El segmento en sí está listo y correcto y todo está bien.

• n \bmod 6=1 : Esto implica que n \bmod 3=1 así que tenemos un elemento extra con módulo 1, este se puede agregar al inicio de la construcción.

• n \bmod 6=2 : construimos basado en el caso anterior, esto implica que n \bmod 3=2 así que tenemos un elemento extra con módulo 2, este se puede agregar al final.

• n \bmod 6=3 : Aquí el caso es diferente porque tenemos un elemento extra de cada tipo (0,1,2), aquí empujaremos al frente $1$ y $2$ y $0$ al final, así que la construcción será como [2,1,1,0,0,1,1,...,0].

• n \bmod 6=4 : construimos basado en el caso anterior, tendremos un $1$ extra, así que podemos agregarlo al frente y todo estará bien.

• n \bmod 6=5 : construimos basado en el caso anterior, tendremos un $2$ extra, podemos agregarlo al frente.

Esto se puede hacer rápidamente con $\mathtt{deque}$, complejidad $\mathcal{O}(n)$ en general.

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
int solve(int n){
    if(n==4){
        cout<<"3 4 1 2\n"; 
        return 0;
    }
    if(n==5){
        cout<<"3 4 1 2 5\n";
        return 0;
    }
    deque<int>p;
    stack<int>m0,m1,m2;
    for(int i=1;i<=n;i++){
        if(i%3==0)m0.push(i);
        if(i%3==1)m1.push(i);
        if(i%3==2)m2.push(i);
    }
    for(int i=0;i<n/6;i++){
        for(int i=0;i<2;i++){
            p.pb(m2.top());
            m2.pop();
        }
        for(int i=0;i<2;i++){
            p.pb(m0.top());
            m0.pop();
        }
        for(int i=0;i<2;i++){
            p.pb(m1.top());
            m1.pop();
        }
    }
    // restantes
    if(n%6==1 || n%6==2){
        p.pf(m1.top());
        m1.pop();
    }
    if(n%6==2){
        p.pb(m2.top());
        m2.pop();
    }
    if(n%6>=3){
        p.pf(m1.top());
        p.pf(m2.top());
        p.pb(m0.top());
        m1.pop();
        m2.pop();
        m0.pop();
    }
    if(n%6>=4){
        p.pb(m1.top());
    }
    
    if(n%6==5){
        p.pf(m2.top());
    }
    for(auto i:p){
        cout<<i<<" ";
    }
    cout<<"\n";
    return 0;
}  

int main() {
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        solve(n);
    }
    return 0;
}