#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif
// mt19937_64 for 64 bit
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int x, int y){
return uniform_int_distribution<int>(x, y)(rng);
}
long long count_triples(vector<int> H){
int n = H.size();
const int OFFSET = n;
vector<vector<int>> at_sum(2 * n + 1), at_diff(2 * n + 1);
for(int i = 0; i < n; i++){
at_sum[i + H[i]].push_back(i);
at_diff[i - H[i] + OFFSET].push_back(i);
}
int ans = 0;
// right-most is highest
for(int k = 0; k < n; k++){
int i = k - H[k];
if(i < 0 || H[i] >= H[k]) continue;
{
int j = k - H[i];
if(H[j] == j - i) ans++;
}
{
int j = i + H[i];
if(H[j] == k - j && k + i != 2 * j) ans++;
}
}
// left-most is highest
for(int i = 0; i < n; i++){
int k = i + H[i];
if(k >= n || H[k] >= H[i]) continue;
{
int j = k - H[k];
if(H[j] == j - i) ans++;
}
{
int j = i + H[k];
if(H[j] == k - j && k + i != 2 * j) ans++;
}
}
// middle is highest
for(int j = 0; j < n; j++){
for(int i: at_sum[j]){
if(H[i] >= H[j] || i >= j) continue;
int Hk = H[j] - H[i];
int k = j + Hk;
if(k < n && H[k] == Hk && H[i] != Hk) {
ans++;
}
}
if(sz(at_sum[j + H[j]]) < sz(at_diff[j - H[j] + OFFSET])){
for(int k: at_sum[j + H[j]]){
if(H[k] >= H[j] || k <= j) continue;
int i = j - H[k];
if(i < 0) continue;
if(H[i] + H[k] == H[j]) ans++;
}
} else{
for(int i: at_diff[j - H[j] + OFFSET]){
if(H[i] >= H[j] || i >= j) continue;
int k = j + H[i];
if(k >= n) continue;
if(H[k] + H[i] == H[j]) ans++;
}
}
}
return ans;
}
std::vector<int> construct_range(int n, int req) {
int mx = 0;
while(true){ // keep running
for(int t = (n==20 ? 1 : sqrt(n)); t * t <= 10 * n; t = max(t + 1,(int)(t * 1.11))){
vector<int> H(n, -1);
vector<bool> used(n + 1, false);
for(int qq = 0; qq < 5; qq++){
set<int> vals;
// return 0;
for(int i = 2; i <= t; i+=2) vals.insert(i);
while(sz(vals) < 2 * t){
int upper = n == 20 ? n/2: 2 * n / 3;
vals.insert(getRand(1, upper) * 2);
}
vector<int> V(all(vals));
for(int diff: V){
for(int sum: V){
if((sum + diff) % 2 == 1) continue;
int i = (sum + diff) / 2;
int h = (sum - diff) / 2;
if(h >= n || h < 1) continue;
if(i < 0 || i >= n) continue;
if(used[i]) continue;
if(h > 0 && h < n){
H[i] = h;
// used[i] = true;
}
}
}
for(int i = 0; i < n; i++){
if(H[i] != -1){
used[i] = true;
}
}
}
int filled = n;
for(int i = 0; i < n; i++){
if(H[i] == -1){
H[i] = getRand(1, 2);
filled--;
}
}
if(n == 20){
H = {2, 1, 1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 3, 2, 3, 4, 1, 2, 1, 3};
}
int got = count_triples(H);
if(got >= req){
return H;
}
}
}
}
