ALGO Anneal

#include <bits/stdc++.h>
namespace Mlxa {
    typedef long long           ll;
    typedef unsigned long long  count_t;
    typedef unsigned long long  index_t;
    using namespace std;

    #define read cin
    #define eol '\n'
    #define all(x) begin(x), end(x)

    template <class A> inline void
    print   (A a)           { cout << a << ' '; }
    template <class A> inline void
    println (A a)           { cout << a << eol; }
    template <class A> inline void
    err     (A a)           { cout << a << ' '; }
    template <class A> inline void
    errln   (A a)           { cout << a << eol; }
    template <class A, class... B> inline void
    println (A a, B... b)   { cout << a << ' '; println(b...); }
    template <class A, class... B> inline void
    errln   (A a, B... b)   { cerr << a << ' '; errln(b...); }
    template <ostream &out, class I> void
    printSeq(I b, I e)      { for(I i=b;i!=e;++i)out<<*i<<' '; out<<'\n'; }
    #ifdef AC
        #define addLog(...) println(__VA_ARGS__)
    #else
        #define addLog(...) (void(0))
    #endif


    count_t s = 19191919LL;
    inline count_t randomNumber ()
    {
        s ^= (s << 21);
        s ^= (s >> 35);
        s ^= (s << 4);
        return s;
    }

} using namespace Mlxa;

/*----------------------------------------------------------
*       Метод отжига:
*
* float T
* float F (T X)
* -----------------------------------------------------------
*   Иннициализация:
*   а) Т = Амплитуда
*   б) x0 = randomNuber()
*       curX = x0
*       minVal = curVal = F(curX)
* -----------------------------------------------------------
*   Итерация:
*   Условия заверешения:
*       а) T = 0.
*       б) Стало ясно что достигнут глоб. мин.
*       в) Выполнили N итераций.
*   Действия:
*       1) Случайное изменение ~ T.
*       Получили:
*           newX, newVal = F(newX).
*       2) Переходим в новую точку если:
*           Произошло событие с вероятностью ~ T
*           (randomNumber() < exp((F(curX) - F(newX)) / T)
*       3) T *= 0.99
* -----------------------------------------------------------
*/

count_t N;
typedef vector<index_t> per_t;
per_t permutation;


void start ()
{
    srand(time(nullptr) + ('2' +'4' + '8' + '1'));
    read >> N;
    for (index_t i = 0; i < N; ++ i)
        permutation.push_back(i);
}

count_t diag[2][10000];

count_t F (const per_t &X)
{
    for (index_t i = 0; i <= 2*N; ++ i)
        diag[0][i] = diag[1][i] = 0;

    for(index_t i = 0; i < N; ++ i)
        ++ diag[0][i + X[i]],
        ++ diag[1][N + i - X[i]];

    count_t result = 0;
    for (index_t i = 0; i <= 2*N; ++ i)
        result += diag[0][i] * (diag[0][i] - 1) / 2,
        result += diag[1][i] * (diag[1][i] - 1) / 2;

    return result;
}

count_t burn ()
{
    per_t   curX    = permutation;
    count_t curVal  = F(curX),
            minVal  = curVal;
    index_t i, j;

    const count_t repeat = max(20000ull, N * N / 2);

    index_t tmp;

    for (double t = -100; t < repeat && curVal; ++ t)
    {
        i   = randomNumber() % N;
        j   = randomNumber() % N;

        tmp = curX[i];
        curX[i] = curX[j];
        curX[j] = tmp;

        curVal = F(curX);

        count_t d = (count_t)(2.71 * exp( -t * 0.019));
        if ( curVal < minVal + d )
            minVal = curVal;
        else
            tmp = curX[i],
            curX[i] = curX[j],
            curX[j] = tmp;
    }

    permutation = curX;
    return minVal;
}

int main ()
{
    start();

    ll cnt = 1;

    while (burn() > 0)
        random_shuffle(all(permutation)), ++ cnt;

    addLog("Burn count  =", cnt);

    for (auto i : permutation)
        print(i + 1);
    println("");

    return 0;
}