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

Розв'язок

Оскільки $p$ є перестановкою, максимальна сума двох значень, яку ми можемо отримати, дорівнює n + n-1 = 2n - 1.

Тепер, для фіксованого значення $x$, знайдемо значення $y$, при яких (x + y) $\text{mod}$ (n+1) = 0.

(x + y) $\text{mod}$ (n+1) = 0, тому x + y = k \cdot (n+1), оскільки суми є додатними, k \in N.

при k=1 \Rightarrow x + y = n+1 \Rightarrow y = n+1-x.

при k=2, x + y = 2n+2, але 2n+2 > 2n-1, тому така сума недосяжна.

Тепер, для фіксованого значення $x$, знайдемо значення $y$, при яких (x + y) $\text{mod}$ (n+1) = n.

(x + y) $\text{mod}$ (n+1) = n, тому x + y = n + k \cdot (n+1) і k \in N.

при k = 0 \Rightarrow x + y = n \Rightarrow y =n - x.

при k = 1, x + y = 2n + 1, 2n + 1 > 2n - 1, тому така сума недосяжна.

Отже, для значення $x$ існує щонайбільше два значення, які можна розмістити як сусіда до $x$, а саме n+1-x , n - x.

коли x = n, значення є $1,0$, оскільки ми не можемо помістити $0$ у перестановку, значення $n$ повинно мати лише одного сусіда, тому значення $n$ має знаходитись або на індексі $1$, або на індексі $n$.

Оскільки кожне значення має щонайбільше два підходящих сусідніх значення, ми можемо будувати перестановку поелементно після визначення індексу значення $n$.

Часова складність $\mathcal{O}(n)$.

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc;
    cin>>tc;
    while(tc -- )
    {
        int n;
        cin>>n;
        int l = 1 , r = n;
        for(int i=1;i<=n;i++)
        {
            cout<<(i%2 ? r-- : l++)<<' ';
        }
        cout<<endl;
    }
}