333 Permutation (Corrigé)

Considérons la construction via les mods, nous n'avons que 3 choix \{0,1,2\}, remarquons un certain motif valide stable, avant cela nous devons identifier les triplets valides

et pour éviter trop de cas à traiter, considérons un long segment répété qui est valide, nous pouvons considérer un segment de [2,2,0,0,1,1], remarquez qu'au pire, seulement 5 éléments resteront à distribuer correctement ! Voici le segment fixe :

Maintenant, considérons les cas restants :

• n \bmod 6=0 : Le segment lui-même est prêt et correct et tout va bien.

• n \bmod 6=1 : Cela implique que n \bmod 3=1 donc nous avons un élément supplémentaire avec mod 1, cela peut être ajouté au début de la construction.

• n \bmod 6=2 : construisez en fonction du cas précédent, cela implique que n \bmod 3=2 donc nous avons un élément supplémentaire avec mod 2, cela peut être ajouté à la fin.

• n \bmod 6=3 : Ici le cas est différent car nous avons un élément supplémentaire de chaque type (0,1,2), ici nous allons pousser $1$ et $2$ à l'avant et $0$ à l'arrière, donc la construction sera comme [2,1,1,0,0,1,1,...,0].

• n \bmod 6=4 : construisez en fonction du cas précédent, nous aurons un $1$ supplémentaire, donc nous pouvons l'ajouter à l'avant et tout va bien.

• n \bmod 6=5 : construisez en fonction du cas précédent, nous aurons un $2$ supplémentaire, nous pouvons l'ajouter à l'avant.

Cela peut être fait rapidement avec $\mathtt{deque}$, Complexité $\mathcal{O}(n)$ au total.

#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();
        }
    }
    // reste
    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;
}