Exam for the Night's Watch (Editorial)

Idea

Let us reformulate the definition of the function $f(p)$. $f(p)$ — the number of indices 1 \le i \le n-2 such that the condition p_i \not\equiv p_{i+1} \pmod{2} holds. Obviously, f(p)\le n-2. At the same time, there are only four arrangements of even and odd numbers that give the result f(p) = n-2.

1. 1,0,0,1,1,0,0,1...

2. 1,1,0,0,1,1,0,0...

3. 0,1,1,0,0,1,1,0...

4. 0,0,1,1,0,0,1,1...

0 — even numbers, 1 — odd numbers. Since we want the permutation to be lexicographically minimal, we will place the smallest number of the corresponding parity. Then it is easy to notice that among all arrangements, the first one will produce the lexicographically smallest permutation. But there is one nuance. When n \equiv 3 \pmod{4}, we will need \lceil \frac{n}{2} \rceil even numbers and \lfloor \frac{n}{2} \rfloor — odd numbers, while we have \lfloor \frac{n}{2} \rfloor — even numbers and \lceil \frac{n}{2} \rceil — odd numbers. In that case, we should build the permutation according to the second pattern, that is, 1,1,0,0,1.... We will maintain two variables first_odd — the smallest odd number that has not yet appeared in the permutation, and similarly first_even — the smallest even one. First, we choose the pattern by which we will build the permutation, and then we iterate over the numbers 3 \le i \le n and choose which number to place, increasing the corresponding number by two.

Thus, the overall complexity is $O(n)$.

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> ans(n);
  int first_odd = 1, first_even = 2;
  if (n % 4 == 3) {
    ans[0] = 1;
    ans[1] = 3;
    first_odd = 5;
  } else {
    ans[0] = 1;
    ans[1] = 2;
    first_odd = 3, first_even = 4;
  }
  for (int i = 2; i < n; i++)
    if (ans[i - 2] & 1) ans[i] = first_even, first_even += 2;
    else ans[i] = first_odd, first_odd += 2;
  for (int i = 0; i < n; i++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
}