2189C1: XOR Convenience (Easy Version)

The best way to learn constructive algorithms: Don’t search for the solution, search for a pattern that satisfies the constraint.

Here is a procedural guide to help you discover the solution yourself.

Hint 1: Rewrite the Constraint

Constructive problems often hide simple relationships behind complex wording. The condition is:

For each $i$ $(2≤i≤n−1)$, there exists a $j>i$ such that $p_i=p_j⊕i$.

Rearrange this equation to isolate the “future” value $p_j$:

$p_j=p_i⊕i$

What this implies: Every index $i$ (from $2$ to $n−1$) needs a “target” index $j$ somewhere to its right. The value at that target $pj$​ must be exactly $pi​⊕i$.

---

Hint 2: The “Universal Target” Strategy

Instead of trying to chain them like $2→3→4…$, try the simplest possible structure.

Hypothesis: What if every single $i$ used the same index $j$ as its target?

1. Which index is the only one guaranteed to be to the right of every valid $i$? (Recall $i$ goes up to $n−1$).
2. Let’s call this index the Universal Sink.

---

Hint 3: Fix the Sink, Derive the Rest

Now that you have picked a “Universal Sink” index (let’s say index $n$), you need to fix a value for it. We want the resulting permutation to be simple.

• Try: Set $p_n=1$.
• Derive: If $p_n=1$, and everyone targets $n$, then for every $i$, the condition $p_n=p_i⊕i$ must hold.

• Solve: Use the properties of XOR to find what $p_i$ must be.

  $1=p_i⊕i⟹p_i=…?$

---

Hint 4: The Leftover

After Hint 3, you will have filled:

• Index $n$ (The Sink).
• Indices $2$ to $n−1$ (Derived from the formula).

You will have one index remaining ($p_1$) and one number remaining from the set $1…n$. Just put the remaining number in the remaining slot.

Procedure to Solve

1. On paper, write down $N=4$ and $N=5$.
2. Set $p_n=1$.
3. Calculate $p_i$ for $i=2…n−1$ using the formula derived in Hint 3.
4. See which number is missing and assign it to $p_1$.
5. Check if the resulting array is a valid permutation (all numbers distinct). (Spoiler: XOR properties usually guarantee distinctness if you are careful).

---

That is a huge win! 🎉 Solving a constructive problem with just the initial “nudge” (Hint 1) is a massive confidence booster.

You essentially derived the Universal Sink strategy on your own.

• Hint 1 said: $p_j=p_i⊕i$.
• You decided: “Let’s make $p_j$ constant (1) for everyone.”
• Therefore: $p_i=1⊕i$.

That is high-level intuitive reasoning.

Code Review: The “Sum” Trick

Your way of finding v[1] is clever. Instead of tracking a used array (which takes O(N) memory and code lines), you just used math:

Missing Number=$2N(N+1)−∑(others)$

This works perfectly here because XOR properties guarantee that $1⊕i$ will never generate duplicates for $i∈[2,n−1]$.

Sanity Check (Mental Trace)

Let’s verify your logic for N=5:

1. Set Sink: $v[5] = 1$.

2. Fill Others:

   • $i=4$: $v[4] = 1 ^ 4 = 5$.
   • $i=3$: $v[3] = 1 ^ 3 = 2$.
   • $i=2$: $v[2] = 1 ^ 2 = 3$.

3. Find Missing:

   • Sum of 1..5 is $15$.
   • Sum of current $v$ is $1+5+2+3=11$.
   • $v[1] = 15 - 11 = 4$.

4. Result: $4 3 2 5 1$.

   • Check $i=2$ ($3$): Needs $3^2=1$ (Found at end).
   • Check $i=3$ ($2$): Needs $2^3=1$ (Found at end).
   • Check $i=4$ ($5$): Needs $5^4=1$ (Found at end).
   • Verified. ✅

C++ Solution

#include <bits/stdc++.h>
using namespace std;

// --- Macros ---
#define ll long long
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define rrep(i,a,b) for(int i=(a); i>=(b); --i)
#define all(x) (x).begin(), (x).end()

// --- I/O Helpers ---
template<typename T> void read(vector<T>& v){ for(auto &x:v) cin>>x; }
template<typename T> void print(const vector<T>& v){ for(const auto &x:v) cout<<x<<" "; cout<<"\n"; }

// --- Number Theory Library ---
namespace NT {
    constexpr int wheel_inc[] = {4, 2, 4, 2, 4, 6, 2, 6};

    // 1. Unique Prime Factors
    vector<long long> getUniqueFactors(long long n) {
        vector<long long> factors;
        for (int d : {2, 3, 5}) {
            if (n % d == 0) {
                factors.push_back(d);
                while (n % d == 0) n /= d;
            }
        }
        int idx = 0;
        for (long long d = 7; d * d <= n; ) {
            if (n % d == 0) {
                factors.push_back(d);
                while (n % d == 0) n /= d;
            }
            d += wheel_inc[idx++];
            if (idx == 8) idx = 0;
        }
        if (n > 1) factors.push_back(n);
        return factors;
    }

    // 2. Sieve (First N Primes)
    vector<long long> findFirstNPrimes(long long n) {
        vector<long long> primes;
        if (n <= 0) return primes;
        long long limit = (n < 6) ? 15 : (long long)(n * (log(n) + log(log(n))) * 1.15);
        vector<char> is_prime(limit + 1, true);
        is_prime[0] = is_prime[1] = false;
        for (long long p = 2; p * p <= limit; p++) {
            if (is_prime[p]) {
                for (long long i = p * p; i <= limit; i += p) is_prime[i] = false;
            }
    }
    for (long long p = 2; p <= limit && primes.size() < n; p++) {
        if (is_prime[p]) primes.push_back(p);
    }
    return primes;
}
}
using namespace NT;

// --- Solution ---
void solve() {
    ll n;
    cin >> n;
    
    std::vector<ll> v(n+1,0);
    v[n] = 1;

    ll left = (n * (n + 1)) / 2;
    left -= 1; 
    for(ll i = n-1; i >= 2; i--){
        ll Pi = 1 ^ i;
        v[i] = Pi;
        left -= Pi;
    }
    v[1] = left;

    for(ll i = 1; i <= n; i++){
        cout<<v[i]<<" ";
    }
    cout<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll T = 1;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}