p416.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;

void read() { cin >> n; }

void solve() {
    // To maximize the risk function (sum of squared differences), we want to
    // pair numbers with maximum differences: (1,n), (2,n-1), (3,n-2), etc.
    // These pairs will be placed at adjacent positions (2i-1, 2i). The key is
    // how to arrange these pairs around the circle. We start with (1,n), then
    // cycle through 4 operations: inverted to back, normal to front, normal to
    // back, inverted to front. This creates large differences in both the
    // i -> i+2 direction and between the inner/outer layers. Something like:
    //
    // S5:   5   , n - 4
    // S3:   n-2 , 3
    // S1:   1   , n
    // S2:   n-1 , 2
    // S4:   4   , n - 3

    list<pair<int, int>> pairs;
    for(int i = 2; 2 * i <= n; i++) {
        pairs.push_back({i, n - i + 1});
    }

    list<int> ans = {1, n};
    for(int idx = 0; idx < n / 2 - 1; idx++) {
        auto [x, y] = pairs.front();
        pairs.pop_front();

        int op = idx % 4;
        if(op == 0) {
            ans.push_back(y);
            ans.push_back(x);
        } else if(op == 1) {
            ans.push_front(x);
            ans.push_front(y);
        } else if(op == 2) {
            ans.push_back(x);
            ans.push_back(y);
        } else {
            ans.push_front(y);
            ans.push_front(x);
        }
    }

    for(auto x: ans) {
        cout << x << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
statement.txt
======================
416. Optimal Dartboard
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A dartboard is a disc divided into n segments, with each segment labeled with a distinct positive integer between 1 and n. That integer indicates the score for hitting the segment. To make the game more interesting, the arrangement of numbers is chosen in such a way that the risk is maximized. The risk is estimated based on the differences in scores of adjacent segments.

We're studying the following 'double-layered' structure of segments in this problem:



I.e., n is always even, and we split the disc into two layers of  parts along the circumference. We enumerate the segments in the following manner: the first segment is some outer segment, the second segment is the corresponding inner segment, the third segment is some adjacent outer segment, etc. An example of this enumeration is shown on the picture above.

The total risk is defined as the sum of squared differences between the scores of adjacent segments. If the value assigned to segment i is ai, then the risk is:

R=∑i=1n(ai-ai+2)2+∑i=1n/2(a2i-1-a2i)2

(we assume an+1=a1 and an+2=a2 in this formula).

You are to place the numbers from 1 through n into the segments in such a way that the total risk R is maximized.

Input
The input file contains an even integer number n (6 ≤ n ≤ 100).

Output
Output n integer numbers: a1, a2,..., an, separated with single spaces. In case there are several possible solutions, output any.

Example(s)
sample input
sample output
10
2 9 7 4 6 5 3 8 10 1

=================
p416.ans1
======================
2 9 7 4 6 5 3 8 10 1

=================
p416.in1
======================
10

=================
