Имитация отжига

import random
import math

def ok(A):
    z = 0
    for i in range(n):
        for j in range(i + 1, n):
            if abs(i - j) == abs(A[i] - A[j]):
                z += 1
    return z

n = int(input())
t = 10000.0
A = list(range(1, n + 1))
random.shuffle(A)
ans = ok(A)
C = list(A)
z = ans

while z > 0:
    i = random.randint(0, n - 1)
    j = random.randint(0, n - 1)
    if i == j:
        continue
    A[i], A[j] = A[j], A[i]
    val = ok(A)
    if val < ans or random.random() < math.exp((ans - val) / t):
        ans = val
        if val == 0:
            C = list(A)
            z = val
            break
    else:
        A[i], A[j] = A[j], A[i]
    t *= 0.99

print(*C)

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

int ok(const vector<int>& A, int n) {
    int z = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (abs(i - j) == abs(A[i] - A[j])) {
                z++;
            }
        }
    }
    return z;
}

int main() {
    srand(time(0));
    int n;
    cin >> n;
    
    double t = 10000.0;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        A[i] = i + 1;
    }
    
    random_shuffle(A.begin(), A.end());
    
    int ans = ok(A, n);
    vector<int> C = A;
    int z = ans;
    
    while (z > 0) {
        int i = rand() % n;
        int j = rand() % n;
        if (i == j) continue;
        
        swap(A[i], A[j]);
        int val = ok(A, n);
        
        double random_value = (double)rand() / RAND_MAX;
        if (val < ans || random_value < exp((ans - val) / t)) {
            ans = val;
            if (val == 0) {
                C = A;
                z = val;
                break;
            }
        } else {
            swap(A[i], A[j]);
        }
        
        t *= 0.99;
    }
    
    for (int num : C) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}