Sum vs MEX#13063

Sum vs MEX (Editorial)

Hint $1$ : however you construct the permutation $p$ , both $i = 1 \sum n p_{i}$ \sum\limits_{i=1}^{n} p_i and MEX( $p_{1}, p_{2}, ..., p_{n}$ p_1 , p_2 , ... , p_n) are fixed.

Hint $2$ : for each $i$ where $i < n$ i < n, you can always get $MEX$ ( $p_{1}, p_{2}, ..., p_{i}$ p_1 , p_2 , ... , p_i) equals $1$ by setting $p_{n} = 1$ p_n = 1.

Solution: Since all integers are divisible by $1$ , we have only to check the condition for $i = n$ i=n , where $sum$ equals $\frac{n \cdot ( n + 1 )}{2}$ \frac{n \cdot (n+1)}{2} , and $MEX$ equals $n + 1$ n+1, $\frac{sum}{mex} = \frac{n}{2}$ \frac{\text{sum}}{\text{mex}} = \frac{n}{2} , so when $n$ is odd , the condition is not fulfilled, so the answer is NO; otherwise, the answer is YES. Any permutation $p$ where $p_{n} = 1$ p_n = 1 is a valid construction.

Time complexity : $O (n)$

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        if(n % 2 == 1)
        {
            cout<<"NO"<<endl;
            continue;
        }
        cout<<"YES"<<endl;
        int ans[n+1];
        for(int i=1;i<=n;i++)
        ans[i] = i;
        swap(ans[1] , ans[n]);
        for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
        cout<<endl;
    }
}