#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
long long count_triples(std::vector<int> a) {
const int n = (int)a.size();
unordered_set<ll> seen;
auto check = [&](int i, int j) -> void {
if (i < 0 || i >= n) return;
if (j < 0 || j >= n) return;
vi cand = {i+a[i], i-a[i], i+a[j], i-a[j], j+a[i], j-a[i], j+a[j], j-a[j]};
for (int k : cand) if (k != i && k != j && k < n && k >= 0) {
array<int, 3> id{i, j, k}, v{a[i], a[j], a[k]}, d{abs(i-j), abs(i-k), abs(j-k)};
sort(id.begin(), id.end());
sort(v.begin(), v.end());
sort(d.begin(), d.end());
if (d == v) seen.insert(id[0]*(ll)1e12+id[1]*(ll)1e6+(ll)id[2]);
}
};
for (int i = 0; i < n; i++) check(i, i-a[i]), check(i, i+a[i]);
ll ans = seen.size();
vvi pk(3*n), nk(3*n);
for (int i = 0; i < n; i++) {
if (i-a[i]+n >= 0) pk[i-a[i]+n].push_back(i);
if (i+a[i]+n < 3*n) nk[i+a[i]+n].push_back(i);
}
for (int i = 0; i < 3*n; i++) reverse(nk[i].begin(), nk[i].end());
for (int j = 0; j < n; j++) if (a[j] <= n) {
int szpk = (int)pk[j-a[j]+n].size();
int sznk = (int)nk[j+a[j]+n].size();
if (szpk < sznk) {
vi &sm = pk[j-a[j]+n];
for (int i : sm) {
if (i == j) break;
int l = j-i;
int k = j+a[i];
int r = k-j;
if (k < 0 || k >= n) continue;
if (r == a[i] && l == a[k] && l != r) ans++;//, cout << i << " " << j << " " << k << endl;
}
}
else {
vi &sm = nk[j+a[j]+n];
for (int k : sm) {
if (k == j) break;
int r = k-j;
int i = j-a[k];
int l = j-i;
if (i < 0 || i >= n) continue;
if (r == a[i] && l == a[k] && l != r) ans++;//, cout << i << " " << j << " " << k << endl;
}
}
}
return ans;
}
std::vector<int> construct_range(int n, int k) {
if (n == 20) {
//vector<pair<int, vi>> dp(1);
//for (int i = 0; i < n; i++) {
// vector<pair<int, vi>> dp2;
// for (int h = 1; h < 10; h++) for (auto [_, a] : dp) {
// a.push_back(h);
// int cnt = i >= 3 ? count_triples(a) : 0;
// dp2.push_back({cnt, a});
// }
// sort(dp2.rbegin(), dp2.rend());
// while (dp2.size() > 10000) dp2.pop_back();
// swap(dp, dp2);
// cout << "Done: " << i << endl;
//}
//return dp[0].second;
return {5, 2, 3, 3, 1, 2, 1, 4, 3, 2, 7, 6, 5, 6, 3, 4, 1, 2, 1, 3};
}
vi ans = {1, 1, 1};
int mx = 0, bseed = 42;
for (int t = 1; t*n <= 1e8; t++) {
int seed = t;
if (n == 500) seed = 24897;
mt19937 rng(seed);
set<int> s;
int bnd = sqrt(n*6);
bnd = uniform_int_distribution<int>(bnd*2/3, bnd*4/3)(rng);
while ((int)s.size() < bnd) {
int x = uniform_int_distribution<int>(-n/2, 3*n/2-1)(rng);
if (x&1) x--;
s.insert(x);
}
vi pts(s.begin(), s.end()), a(n, 1e9);
int m = (int)pts.size();
for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) if ((pts[i]+pts[j])/2 >= 0 && (pts[i]+pts[j])/2 < n) a[(pts[i]+pts[j])/2] = min(a[(pts[i]+pts[j])/2], (abs(pts[i]-pts[j]))/2);
for (int i = 0; i < n; i++) if (a[i] == 1e9) a[i] = uniform_int_distribution<int>(1, 2)(rng);
int count = count_triples(a);
if (count > mx) mx = count, ans = a, bseed = seed;
if (5*(mx/(float)k) >= 5.0) break;
}
//cout << "Score: " << setprecision(2) << fixed << 5*(mx/(float)k) << endl;
//cout << "Seed: " << bseed << endl;
return ans;
}
