333 Перестановка (Розбір)

Розглянемо конструкцію через модулі, у нас лише 3 вибори \{0,1,2\}, звернімо увагу на деякий стабільний дійсний шаблон, перед цим ми повинні визначити дійсні трійки

і щоб уникнути занадто великої кількості випадків, давайте розглянемо деякий довгий повторюваний сегмент, який є дійсним, ми можемо розглянути сегмент [2,2,0,0,1,1], зверніть увагу, що в найгіршому випадку залишиться лише 5 елементів, які потрібно правильно розподілити! Ось фіксований сегмент:

Тепер розглянемо залишкові випадки:

• n \bmod 6=0 : Сегмент сам по собі готовий і правильний, і все в порядку.

• n \bmod 6=1 : Це означає, що n \bmod 3=1, отже, у нас є додатковий елемент з модулем 1, його можна додати на початок конструкції.

• n \bmod 6=2 : Конструюємо на основі попереднього випадку, це означає, що n \bmod 3=2, отже, у нас є додатковий елемент з модулем 2, його можна додати в кінець.

• n \bmod 6=3 : Тут випадок інший, тому що у нас є додатковий елемент кожного типу (0,1,2), тут ми перемістимо 1 і 2 на початок, а 0 в кінець, тому конструкція буде виглядати як [2,1,1,0,0,1,1,...,0].

• n \bmod 6=4 : Конструюємо на основі попереднього випадку, у нас буде додатковий $1$, тому ми можемо додати його на початок, і все в порядку.

• n \bmod 6=5 : Конструюємо на основі попереднього випадку, у нас буде додатковий 2, ми можемо додати його на початок.

Це можна зробити швидко за допомогою $\mathtt{deque}$, складність $\mathcal{O}(n)$ в цілому.

#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();
        }
    }
    // залишки
    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;
}