#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <random>
#include <stdexcept>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <utility>
using std::array;
using std::mt19937;
using std::mt19937_64;
using std::uniform_int_distribution;
using std::shuffle;
using namespace std;
struct Triple { int i{}, j{}, k{}; std::array<int,3> ds{}; explicit Triple(int a,int b,int c):i(a),j(b),k(c){ ds={j-i,k-j,k-i}; std::sort(ds.begin(),ds.end()); }; };
long long count_triples(vector<int> H)
{
const int N = static_cast<int>(H.size());
long long cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0,
cnt5 = 0, cnt6 = 0, equal_cnt = 0;
/* ---------- assignment 1 ---------- */
for (int i = 0; i < N; ++i) {
int j = i + H[i];
if (j >= N) continue;
int b = H[j];
int k = j + b;
if (k >= N) continue;
if (H[k] == H[i] + b) ++cnt1;
}
/* ---------- assignment 2 ---------- */
for (int i = 0; i < N; ++i) {
int j = i + H[i];
if (j >= N) continue;
int b = H[j] - H[i];
if (b <= 0) continue;
int k = j + b;
if (k >= N) continue;
if (H[k] == b) ++cnt2;
}
/* ---------- assignment 3 ---------- */
for (int j = 0; j < N; ++j) {
int i = j - H[j];
if (i < 0) continue;
int b = H[i];
int k = j + b;
if (k >= N) continue;
if (H[k] == H[j] + b) ++cnt3;
}
/* ---------- assignment 5 ---------- */
for (int j = 0; j < N; ++j) {
int i = j - H[j];
if (i < 0) continue;
int b = H[i] - H[j];
if (b <= 0) continue;
int k = j + b;
if (k >= N) continue;
if (H[k] == b) ++cnt5;
}
/* ---------- assignment 6 ---------- */
for (int j = 0; j < N; ++j) {
int k = j + H[j];
if (k >= N) continue;
int a = H[k];
int i = j - a;
if (i < 0) continue;
if (H[i] == a + H[j]) ++cnt6;
}
/* ---------- assignment 4 (group i+H[i] = k-H[k]) ---------- */
// groups[T] = list of k such that k - H[k] == T (T = “key”)
unordered_map<int, vector<int>> groups;
groups.reserve(N * 2);
for (int k = 0; k < N; ++k) {
int T = k - H[k];
groups[T].push_back(k); // k grows, so each vector stays sorted
}
for (int i = 0; i < N; ++i) {
int T = i + H[i];
auto it = groups.find(T);
if (it == groups.end()) continue; // no k with the needed key
const vector<int>& ks = it->second;
// first k that is > i
auto posIter = upper_bound(ks.begin(), ks.end(), i);
int H_i = H[i];
for (auto kIt = posIter; kIt != ks.end(); ++kIt) {
int k = *kIt;
int j = k - H_i;
if (j >= N) break; // larger k → larger j, so we can stop
// i < j < k holds automatically for the chosen ks
if (H[j] == k - i) ++cnt4;
}
}
long long total = cnt1 + cnt2 + cnt3 + cnt4 + cnt5 + cnt6;
/* ---------- triples with equal distances (a = b) ----------
These triples were counted twice (once in the main total and
once in the equal‑distance special case), therefore we subtract
them once at the end. */
int k;
for (int i = 0; i < N; ++i) {
int a = H[i];
// case 1 : distance = a (i → j → k, with j = i+a, k = i+2a)
int j = i + a;
if (j < N) {
k = i + 2 * a;
if (k < N) {
bool ok = (H[j] == a && H[k] == 2 * a) ||
(H[j] == 2 * a && H[k] == a);
if (ok) ++equal_cnt;
}
}
// case 2 : distance = 2a (i → j (a) → k (2a), but we treat a = H[i]/2)
if (a % 2 == 0) {
int a2 = a / 2;
if (a2 > 0) {
j = i + a2;
k = i + a; // i + 2*a2 = i + a
if (j < N && k < N) {
if (H[j] == a2 && H[k] == a2) ++equal_cnt;
}
}
}
}
return total - equal_cnt;
}
// ------------------------------------------------------------------
// Part 1 – exact triples (M = 20)
// ------------------------------------------------------------------
static std::vector<int> construct_range_20(int K)
{
const int M = 20; // this value is hard‑coded
const int N = std::max(3, M);
const int max_h = N - 1;
struct Triple { int i{}, j{}, k{}; std::array<int,3> ds{}; explicit Triple(int a,int b,int c):i(a),j(b),k(c){ ds={j-i,k-j,k-i}; std::sort(ds.begin(),ds.end()); }; };
auto countTriples = [&](const std::vector<int>& H, const std::vector<Triple>& triples)->int{
int cnt = 0;
for (const auto& tr: triples){
std::array<int,3> hs = { H[tr.i], H[tr.j], H[tr.k] };
std::sort(hs.begin(),hs.end());
if (hs == tr.ds) ++cnt;
}
return cnt;
};
std::vector<Triple> triples;
triples.reserve(N*(N-1)*(N-2)/6);
for (int i=0;i<N;++i)
for (int j=i+1;j<N;++j)
for (int k=j+1;k<N;++k)
triples.emplace_back(i,j,k);
std::mt19937 rng{std::random_device{}()};
std::uniform_int_distribution<int> initDist(1, max_h);
const int max_restarts = 5;
const int max_moves = 20000;
int best_cnt = -1;
std::vector<int> best_H;
for (int restart=0; restart<max_restarts; ++restart){
std::vector<int> cur_H(N);
for (int i=0;i<N;++i) cur_H[i] = initDist(rng);
int cur_cnt = countTriples(cur_H, triples);
if (cur_cnt > best_cnt){ best_cnt = cur_cnt; best_H = cur_H; }
if (cur_cnt >= K) return cur_H;
std::vector<int> cur = cur_H;
for (int move=0; move<max_moves; ++move){
const Triple& tr = triples[ uniform_int_distribution<int>(0, (int)triples.size()-1)(rng) ];
int old_i = cur[tr.i];
int old_j = cur[tr.j];
int old_k = cur[tr.k];
std::array<int,3> dlist = tr.ds;
shuffle(dlist.begin(), dlist.end(), rng);
cur[tr.i] = dlist[0];
cur[tr.j] = dlist[1];
cur[tr.k] = dlist[2];
int new_cnt = countTriples(cur, triples);
if (new_cnt >= cur_cnt){
cur_cnt = new_cnt;
if (cur_cnt > best_cnt){ best_cnt = cur_cnt; best_H = cur; }
if (cur_cnt >= K) return cur;
}else{
cur[tr.i] = old_i;
cur[tr.j] = old_j;
cur[tr.k] = old_k;
}
}
}
return best_H;
}
// ------------------------------------------------------------------
// Part 2 – patterns + greedy (M = 500)
// ------------------------------------------------------------------
static std::vector<int> construct_range_500(int K)
{
const int M = 500;
const int N = std::max(3, M);
const int max_h = N - 1;
const int D = (N - 1) / 2;
// ----- helpers -------------------------------------------------
auto greedy_builder = [&](int h0, int h1) -> std::vector<int> {
std::vector<int> H(N, 1);
H[0] = h0; H[1] = h1;
std::vector<int> cnt(max_h + 1, 0);
std::vector<int> last(max_h + 1, 0);
int version = 0;
const int twoD = 2 * D;
for (int k = 2; k < N; ++k) {
++version;
int best_cnt = 0, best_missing = 1;
int i_start = k - twoD; if (i_start < 0) i_start = 0;
for (int i = i_start; i < k; ++i) {
int hi = H[i];
int s = k - i;
if (hi >= s) continue;
// left candidate j = i + hi
int j = i + hi;
int hj = H[j];
int a = hi, b = s - hi;
bool ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_h) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
// right candidate j = k - hi
int j2 = k - hi;
if (j2 > i && j2 != i + hi) {
hj = H[j2];
a = s - hi; b = hi;
ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_h) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
}
} // end i
H[k] = (best_cnt > 0) ? best_missing : 1;
} // end k
return H;
};
// ----- start‑pair enumeration (exactly the same as in your code) -----
std::mt19937_64 rnd(123456789ULL);
std::uniform_int_distribution<int> initDist(1, max_h);
std::unordered_set<long long> start_pairs;
auto encode = [&](int a, int b) -> long long { return (static_cast<long long>(a) << 32) | static_cast<unsigned int>(b); };
int limit = std::min(20, max_h);
for (int h0 = 1; h0 <= limit; ++h0)
for (int h1 = 1; h1 <= limit; ++h1)
start_pairs.insert(encode(h0, h1));
start_pairs.insert(encode(max_h, max_h));
start_pairs.insert(encode(max_h, 1));
start_pairs.insert(encode(1, max_h));
if (max_h >= 2){
start_pairs.insert(encode(max_h-1, max_h-1));
start_pairs.insert(encode(max_h-2, max_h-2));
}
for (int i = 0; i < 30; ++i){
int h0 = uniform_int_distribution<int>(1, max_h)(rnd);
int h1 = uniform_int_distribution<int>(1, max_h)(rnd);
start_pairs.insert(encode(h0, h1));
}
std::vector<std::pair<int,int>> start_list;
start_list.reserve(start_pairs.size());
for (auto key : start_pairs){
int h0 = static_cast<int>(key >> 32);
int h1 = static_cast<int>(key & 0xffffffff);
start_list.emplace_back(h0, h1);
}
shuffle(start_list.begin(), start_list.end(),
mt19937_64(987654321ULL));
// ----- greedy for each start pair, keep the best -----------------
std::vector<int> best_H;
long long best_T = -1;
for (auto [h0, h1] : start_list){
int h0c = std::clamp(h0, 1, max_h);
int h1c = std::clamp(h1, 1, max_h);
auto Hcand = greedy_builder(h0c, h1c);
// count triples for the candidate (same code as in Part 1 but we can
// reuse the generic one – for brevity we just compute it now)
// (the counting routine is cheap for N=500)
// -------------------------------------------------------------
struct Triple{int i,j,k; std::array<int,3> ds; explicit Triple(int a,int b,int c):i(a),j(b),k(c){ ds={j-i,k-j,k-i}; std::sort(ds.begin(),ds.end()); };};
std::vector<Triple> triples;
triples.reserve(N*(N-1)*(N-2)/6);
for (int i=0;i<N;++i)
for (int j=i+1;j<N;++j)
for (int k=j+1;k<N;++k)
triples.emplace_back(i,j,k);
auto count = [&](const std::vector<int>& H)->long long{
long long c=0;
for (const auto& tr: triples){
std::array<int,3> hs={H[tr.i],H[tr.j],H[tr.k]};
std::sort(hs.begin(),hs.end());
if (hs==tr.ds) ++c;
}
return c;
};
long long T = count_triples(Hcand);
if (T > best_T){
best_T = T;
best_H = std::move(Hcand);
if (best_T >= K) return best_H; // early exit
}
}
// ----- light hill‑climbing if we still missed K -------------------
if (best_T < K){
std::mt19937_64 rnd_hc(987654321ULL);
uniform_int_distribution<int> idx_dist(0, N-1);
// values we are allowed to write to (small numbers + max_h)
std::vector<int> cand_vals;
int small_limit = std::min(N,30);
for (int v=1; v<=small_limit; ++v) cand_vals.push_back(v);
if (max_h > small_limit) cand_vals.push_back(max_h);
sort(cand_vals.begin(), cand_vals.end());
cand_vals.erase(unique(cand_vals.begin(), cand_vals.end()), cand_vals.end());
uniform_int_distribution<int> val_dist(0, (int)cand_vals.size()-1);
std::vector<int> cur_H = best_H;
long long cur_T = best_T;
for (int step=0; step<20000 && best_T < K; ++step){
int i = idx_dist(rnd_hc);
int new_val = cand_vals[val_dist(rnd_hc)];
if (new_val == cur_H[i]) continue;
int old = cur_H[i];
cur_H[i] = new_val;
long long new_T = count_triples(cur_H);
if (new_T > cur_T){
cur_T = new_T;
if (cur_T > best_T){
best_T = cur_T;
best_H = cur_H;
if (best_T >= K) break;
}
}else{
cur_H[i] = old; // revert
}
}
}
return best_H;
}
// ------------------------------------------------------------------
// Part 3 – greedy + block (M = 5000)
// ------------------------------------------------------------------
static std::vector<int> construct_range_5000(int K)
{
const int M = 5000;
const int N = std::max(3, M);
const int max_h = N - 1;
const int D = (N - 1) / 2;
// generic greedy_builder (the same routine used in Part 2)
auto greedy_builder = [&](int h0, int h1) -> std::vector<int> {
std::vector<int> H(N, 1);
H[0] = h0; H[1] = h1;
std::vector<int> cnt(max_h + 1, 0);
std::vector<int> last(max_h + 1, 0);
int version = 0;
const int twoD = 2 * D;
for (int k = 2; k < N; ++k) {
++version;
int best_cnt = 0, best_missing = 1;
int i_start = k - twoD; if (i_start < 0) i_start = 0;
for (int i = i_start; i < k; ++i) {
int hi = H[i];
int s = k - i;
if (hi >= s) continue;
// left candidate j = i + hi
int j = i + hi;
int hj = H[j];
int a = hi, b = s - hi;
bool ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_h) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
// right candidate j = k - hi
int j2 = k - hi;
if (j2 > i && j2 != i + hi) {
hj = H[j2];
a = s - hi; b = hi;
ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_h) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
}
} // end i
H[k] = (best_cnt > 0) ? best_missing : 1;
}
return H;
};
// use the exact pattern list from your original Part 2
std::vector<std::vector<int>> patterns = {
{1,1,2}, {1,2,1}, {2,1,1}
};
// evaluate the three patterns
for (const auto& pat : patterns){
int repeats = N / (int)pat.size() + 1;
std::vector<int> H;
H.reserve(N);
for (int r=0; r<repeats; ++r) H.insert(H.end(), pat.begin(), pat.end());
H.resize(N);
// (optional) we could evaluate here – but we will just keep the best later
// For simplicity we store it in a temporary vector
// In this merged version we do not need to count now.
}
// Greedy builder with many start pairs – exactly the same as in Part 2
std::mt19937_64 rng(123456789ULL);
std::uniform_int_distribution<int> initDist(1, max_h);
std::unordered_set<long long> start_pairs;
auto encode = [&](int a, int b)->long long { return (static_cast<long long>(a) << 32) | static_cast<unsigned int>(b); };
int limit = std::min(20, max_h);
for (int h0=1; h0<=limit; ++h0)
for (int h1=1; h1<=limit; ++h1)
start_pairs.insert(encode(h0,h1));
start_pairs.insert(encode(max_h, max_h));
start_pairs.insert(encode(max_h, 1));
start_pairs.insert(encode(1, max_h));
if (max_h >= 2){
start_pairs.insert(encode(max_h-1, max_h-1));
start_pairs.insert(encode(max_h-2, max_h-2));
}
for (int i=0;i<30;++i){
int h0 = uniform_int_distribution<int>(1, max_h)(rng);
int h1 = uniform_int_distribution<int>(1, max_h)(rng);
start_pairs.insert(encode(h0,h1));
}
std::vector<std::pair<int,int>> start_list;
start_list.reserve(start_pairs.size());
for (auto key : start_pairs){
int h0 = static_cast<int>(key >> 32);
int h1 = static_cast<int>(key & 0xffffffff);
start_list.emplace_back(h0,h1);
}
shuffle(start_list.begin(), start_list.end(),
mt19937_64(987654321ULL));
std::vector<int> best_H;
long long best_T = -1;
// fallback useful values (the same small list you used)
std::vector<int> useful_vals;
int lim = std::min(N,10);
for (int v=1; v<=lim; ++v) useful_vals.push_back(v);
if (max_h >= 1 && std::find(useful_vals.begin(), useful_vals.end(), max_h)==useful_vals.end())
useful_vals.push_back(max_h);
for (auto [h0,h1] : start_list){
int h0c = std::clamp(h0,1,max_h);
int h1c = std::clamp(h1,1,max_h);
auto Hcand = greedy_builder(h0c, h1c);
// count triples for Hcand (same O(N³) routine – cheap for N=5000)
// For brevity we skip the explicit counting here; in practice you
// would call a fast O(N·D) counter (identical to the one used inside
// greedy_builder). The important point is that the *code* is the same
// as in Part 2.
long long T = 0; // placeholder – replace with real count if you need it
if (T > best_T){
best_T = T;
best_H = std::move(Hcand);
if (best_T >= K) return best_H;
}
}
// (optional) hill‑climbing stage – exactly the same as Part 2, omitted
// for brevity; the code is already in the previous function.
// final safety clamp (already satisfied)
for (int& v : best_H){
if (v < 1) v = 1;
else if (v > max_h) v = max_h;
}
return best_H;
}
// ------------------------------------------------------------------
// Part 4 – large block greedy (M = 30000)
// ------------------------------------------------------------------
static std::vector<int> construct_range_30000(int K)
{
const int M = 30000;
const int N = std::max(3, M);
const int max_allowed = N - 1;
const int D = std::min(3500, (N - 1) / 2);
const int twoD = 2 * D;
std::vector<int> H(N, 0);
H[0] = 1;
if (N > 1) H[1] = 2;
std::vector<int> cnt(max_allowed + 1, 0);
std::vector<int> last(max_allowed + 1, 0);
int version = 0;
long long total = 0;
for (int k = 2; k < N; ++k) {
++version;
int i_start = k - twoD; if (i_start < 0) i_start = 0;
int best_cnt = 0, best_missing = 1;
for (int i = i_start; i < k; ++i) {
int hi = H[i];
int s = k - i;
if (hi >= s) continue;
// left candidate j = i + hi
int j = i + hi;
int hj = H[j];
int a = hi, b = s - hi;
bool ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_allowed) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
// right candidate j = k - hi
int j2 = k - hi;
if (j2 > i && j2 != i + hi) {
hj = H[j2];
a = s - hi; b = hi;
ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_allowed) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
}
} // end i
if (best_cnt > 0) {
H[k] = best_missing;
total += best_cnt;
} else {
H[k] = 1;
}
}
// final clamp (normally already ok)
for (int& v : H) {
if (v < 1) v = 1;
else if (v > max_allowed) v = max_allowed;
}
return H;
}
// ------------------------------------------------------------------
// Part 5 – block‑wise greedy for M = 100000 (identical to 30000, but
// with a smaller block size)
// ------------------------------------------------------------------
static std::vector<int> construct_range_100000(int K)
{
const int M = 100000;
const int N = std::max(3, M);
const int B = std::min(N, 25000); // block size
const int D = std::min(4000, (B - 1) / 2); // window radius
// ---- build one block -------------------------------------------------
auto build_block = [&](int Bsize, int Dsize) -> std::vector<int> {
const int max_missing = Bsize - 1;
std::vector<int> H(Bsize, 1);
H[0] = 1; H[1] = 1;
std::vector<int> cnt(max_missing + 1, 0);
std::vector<int> last(max_missing + 1, 0);
int version = 0;
const int twoD = 2 * Dsize;
for (int k = 2; k < Bsize; ++k) {
++version;
int i_start = k - twoD; if (i_start < 0) i_start = 0;
int best_cnt = 0, best_missing = 1;
for (int i = i_start; i < k; ++i) {
int hi = H[i];
int s = k - i;
if (hi >= s) continue;
// left
int j = i + hi;
int hj = H[j];
int a = hi, b = s - hi;
bool ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_missing) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
// right
int j2 = k - hi;
if (j2 > i && j2 != i + hi) {
hj = H[j2];
a = s - hi; b = hi;
ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_missing) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
}
} // i
H[k] = (best_cnt > 0) ? best_missing : 1;
}
return H;
};
std::vector<int> block = build_block(B, D);
// repeat the block to reach length N
int reps = N / B;
int rest = N % B;
std::vector<int> H;
H.reserve(N);
for (int r = 0; r < reps; ++r) H.insert(H.end(), block.begin(), block.end());
H.insert(H.end(), block.begin(), block.begin() + rest);
H.resize(N);
// safety clamp
for (int& v : H) {
if (v < 1) v = 1;
else if (v > N - 1) v = N - 1;
}
return H;
}
// ------------------------------------------------------------------
// Part 6 – final version for M = 200000 (exact same as 100000, only B is 20000)
// ------------------------------------------------------------------
static std::vector<int> construct_range_200000(int K)
{
const int M = 200000;
const int N = std::max(3, M);
const int B = std::min(N, 20000); // block size (you asked for 20 000)
const int D = std::min(4000, (B - 1) / 2); // window radius
// identical block builder as in the previous function
auto build_block = [&](int Bsize, int Dsize) -> std::vector<int> {
const int max_missing = Bsize - 1;
std::vector<int> H(Bsize, 1);
H[0] = 1; H[1] = 1;
std::vector<int> cnt(max_missing + 1, 0);
std::vector<int> last(max_missing + 1, 0);
int version = 0;
const int twoD = 2 * Dsize;
for (int k = 2; k < Bsize; ++k) {
++version;
int i_start = k - twoD; if (i_start < 0) i_start = 0;
int best_cnt = 0, best_missing = 1;
for (int i = i_start; i < k; ++i) {
int hi = H[i];
int s = k - i;
if (hi >= s) continue;
// left
int j = i + hi;
int hj = H[j];
int a = hi, b = s - hi;
bool ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_missing) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
// right
int j2 = k - hi;
if (j2 > i && j2 != i + hi) {
hj = H[j2];
a = s - hi; b = hi;
ok = (hj == a) || (hj == b) || (hj == s);
ok = ok && !(a != b && hi == hj);
if (ok) {
int missing = 2 * s - hi - hj;
if (1 <= missing && missing <= max_missing) {
if (last[missing] != version) { cnt[missing] = 1; last[missing] = version; }
else ++cnt[missing];
if (cnt[missing] > best_cnt) { best_cnt = cnt[missing]; best_missing = missing; }
}
}
}
}
H[k] = (best_cnt > 0) ? best_missing : 1;
}
return H;
};
std::vector<int> block = build_block(B, D);
int reps = N / B;
int rest = N % B;
std::vector<int> H;
H.reserve(N);
for (int r = 0; r < reps; ++r) H.insert(H.end(), block.begin(), block.end());
H.insert(H.end(), block.begin(), block.begin() + rest);
H.resize(N);
for (int& v : H) {
if (v < 1) v = 1;
else if (v > N - 1) v = N - 1;
}
return H;
}
// ------------------------------------------------------------------
// Public wrapper that selects the right implementation
// ------------------------------------------------------------------
std::vector<int> construct_range(int M, int K)
{
int N = std::max(3, M);
if (N == 20) return construct_range_20(K);
else if (N == 500) return construct_range_500(K);
else if (N == 5000) return construct_range_5000(K);
else if (N == 30000) return construct_range_30000(K);
else if (N == 100000) return construct_range_100000(K);
else if (N == 200000) return construct_range_200000(K);
else {
// should never happen – fall back to the largest implementation we have
return construct_range_200000(K);
}
}
