Average Student
Time limit: 1 s.
Memory limit: 256 MB
Your teacher knows you are good at problem solving, so they gave you a slightly harder challenge than usual.
You are given an integer \(n\). Your task is to construct a permutation of the integers from \(1\) to \(n\).
However, the teacher adds a special condition: the permutation must be “stable”, meaning that no three consecutive elements should form an arithmetic progression.
A permutation is an arrangement of the numbers \(1\) to \(n\) where each number appears exactly once.
In other words, for every index \(i\) such that \(2 \le i \le n-1\), it must hold that:
\(p[i] \cdot 2 \ne p[i-1] + p[i+1].\)
If there are multiple valid permutations, you may output any of them.
Input
A single integer \(n\) \((1 \le n \le 10^6)\).
Output
Output a single line containing a permutation of length \(n\) satisfying the condition.
If multiple answers exist, print any valid one.
Scoring
In this problem, each test case will be scored separately. Your score is the sum of scores for all test cases.
Examples
Input
1
Output
1
Input
5
Output
3 4 1 2 5
Note
For \(n = 1\), the answer is simply \([1]\).
For \(n = 5\), one valid construction is \([3,4,1,2,5]\).
Check all consecutive triples:
- \((3,4,1)\) is not an arithmetic progression
- \((4,1,2)\) is not an arithmetic progression
- \((1,2,5)\) is not an arithmetic progression
So the condition is satisfied.
Solution
Start with the permutation \([1]\). From a valid permutation, first append all values of the form \(2x-1\) that do not exceed \(n\), then all values of the form \(2x\).
An arithmetic progression among three new values would, after reversing the transformation, give an arithmetic progression in the previous permutation. A triple crossing between the odd and even parts cannot be an arithmetic progression because its first and third values have different parity.
The construction takes \(O(N)\) time and memory.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> permutation = {1};
while ((int)permutation.size() < n) {
vector<int> next;
next.reserve(n);
for (int x : permutation) {
if (2 * x - 1 <= n) {
next.push_back(2 * x - 1);
}
}
for (int x : permutation) {
if (2 * x <= n) {
next.push_back(2 * x);
}
}
permutation.swap(next);
}
for (int x : permutation) {
cout << x << ' ';
}
cout << '\n';
}