# Project Euler 576
# Irrational Jumps — piecewise S(l,g,d) merge for max sum.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function sqrt(x: f64) -> f64
function fabs(x: f64) -> f64
function floor(x: f64) -> f64
}
struct Seg {
ends: ptr<f64>,
vals: ptr<f64>,
n: i32
}
function sift_down(arr: ptr<f64>, start: i64, end: i64) -> void {
let mut root: i64 = start
while 2 * root + 1 < end {
let mut child: i64 = 2 * root + 1
if child + 1 < end {
if arr[child] < arr[child + 1] {
child = child + 1
}
}
if arr[root] < arr[child] {
let tmp: f64 = arr[root]
arr[root] = arr[child]
arr[child] = tmp
root = child
} else {
return
}
}
}
function sort_doubles(arr: ptr<f64>, n: i64) -> void {
if n < 2 { return }
let mut start: i64 = n / 2
while start > 0 {
start = start - 1
sift_down(arr, start, n)
}
let mut end: i64 = n
while end > 1 {
end = end - 1
let tmp: f64 = arr[0]
arr[0] = arr[end]
arr[end] = tmp
sift_down(arr, 0, end)
}
}
function bisect_left(a: ptr<f64>, n: i32, x: f64) -> i32 {
let mut lo: i32 = 0
let mut hi: i32 = n
while lo < hi {
let mid: i32 = lo + (hi - lo) / 2
if a[mid] < x {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
function findp(parent: ptr<i32>, i0: i32) -> i32 {
let mut i: i32 = i0
while parent[i] != i {
parent[i] = parent[parent[i]]
i = parent[i]
}
return i
}
function build_piecewise(l: f64, g: f64) -> Seg {
let domain_end: f64 = 1.0 - g
let mut K: i32 = (1.5 / g) as i32
if K < 10 { K = 10 }
while true {
if K > 4000000 {
return Seg { ends: null, vals: null, n: 0 }
}
let starts: ptr<f64> = malloc((K as i64) * 8) as ptr<f64>
let ends_arr: ptr<f64> = malloc((K as i64) * 8) as ptr<f64>
let labels: ptr<i32> = malloc((K as i64) * 4) as ptr<i32>
let nint: i32 = 0
let endpoints: ptr<f64> = malloc(((2 * K + 2) as i64) * 8) as ptr<f64>
let nep: i32 = 0
endpoints[0] = 0.0
nep = 1
endpoints[1] = domain_end
nep = 2
let mut x: f64 = 0.0
let mut k: i32 = 1
while k <= K {
x = x + l
x = x - floor(x)
let s: f64 = x - g
let e: f64 = x
if e <= 0.0 || s >= domain_end {
k = k + 1
continue
}
let mut ss: f64 = s
let mut ee: f64 = e
if ss < 0.0 { ss = 0.0 }
if ee > domain_end { ee = domain_end }
if ss < ee {
starts[nint] = ss
ends_arr[nint] = ee
labels[nint] = k
endpoints[nep] = ss
nep = nep + 1
endpoints[nep] = ee
nep = nep + 1
nint = nint + 1
}
k = k + 1
}
sort_doubles(endpoints, nep as i64)
let nu: i32 = 0
let mut i: i32 = 0
while i < nep {
if nu == 0 || endpoints[i] != endpoints[nu - 1] {
endpoints[nu] = endpoints[i]
nu = nu + 1
}
i = i + 1
}
let num_cells: i32 = nu - 1
let parent: ptr<i32> = malloc(((num_cells + 1) as i64) * 4) as ptr<i32>
let values: ptr<i32> = calloc(num_cells as i64, 4) as ptr<i32>
i = 0
while i <= num_cells {
parent[i] = i
i = i + 1
}
let mut t: i32 = 0
while t < nint {
let bi: i32 = bisect_left(endpoints, nu, starts[t])
let bj: i32 = bisect_left(endpoints, nu, ends_arr[t])
let mut idx: i32 = findp(parent, bi)
while idx < bj {
values[idx] = labels[t]
parent[idx] = idx + 1
idx = findp(parent, idx)
}
t = t + 1
}
if findp(parent, 0) == num_cells {
let seg_ends: ptr<f64> = malloc(((num_cells + 1) as i64) * 8) as ptr<f64>
let seg_vals: ptr<f64> = malloc(((num_cells + 1) as i64) * 8) as ptr<f64>
let seg_n: i32 = 0
let mut curr: i32 = values[0]
i = 1
while i < num_cells {
if values[i] != curr {
seg_ends[seg_n] = endpoints[i]
seg_vals[seg_n] = (curr as f64) * l
seg_n = seg_n + 1
curr = values[i]
}
i = i + 1
}
seg_ends[seg_n] = domain_end
seg_vals[seg_n] = (curr as f64) * l
seg_n = seg_n + 1
free(starts)
free(ends_arr)
free(labels)
free(endpoints)
free(parent)
free(values)
return Seg { ends: seg_ends, vals: seg_vals, n: seg_n }
}
free(starts)
free(ends_arr)
free(labels)
free(endpoints)
free(parent)
free(values)
K = K * 2
}
return Seg { ends: null, vals: null, n: 0 }
}
function hpush(heap_keys: ptr<f64>, heap_ids: ptr<i32>, hn0: i32, key: f64, id: i32) -> i32 {
let mut n: i32 = hn0
let mut i: i32 = n
n = n + 1
heap_keys[i] = key
heap_ids[i] = id
while i > 0 {
let p: i32 = (i - 1) / 2
if heap_keys[p] <= heap_keys[i] { break }
let tk: f64 = heap_keys[p]
let ti: i32 = heap_ids[p]
heap_keys[p] = heap_keys[i]
heap_ids[p] = heap_ids[i]
heap_keys[i] = tk
heap_ids[i] = ti
i = p
}
return n
}
function hpop(heap_keys: ptr<f64>, heap_ids: ptr<i32>, hn0: i32, out_id: ptr<i32>) -> i32 {
out_id[0] = heap_ids[0]
let mut n: i32 = hn0 - 1
heap_keys[0] = heap_keys[n]
heap_ids[0] = heap_ids[n]
let mut i: i32 = 0
while true {
let l: i32 = 2 * i + 1
let rg: i32 = 2 * i + 2
let mut sm: i32 = i
if l < n {
if heap_keys[l] < heap_keys[sm] { sm = l }
}
if rg < n {
if heap_keys[rg] < heap_keys[sm] { sm = rg }
}
if sm == i { break }
let tk: f64 = heap_keys[i]
let ti: i32 = heap_ids[i]
heap_keys[i] = heap_keys[sm]
heap_ids[i] = heap_ids[sm]
heap_keys[sm] = tk
heap_ids[sm] = ti
i = sm
}
return n
}
function merge_max_sum(seg_ends_arr: ptr<ptr<f64> >, seg_vals_arr: ptr<ptr<f64> >, seg_n_arr: ptr<i32>, P: i32, domain_end: f64) -> f64 {
let idx: ptr<i32> = calloc(P as i64, 4) as ptr<i32>
let cur: ptr<f64> = malloc((P as i64) * 8) as ptr<f64>
let mut total: f64 = 0.0
let mut i: i32 = 0
while i < P {
cur[i] = seg_vals_arr[i][0]
total = total + cur[i]
i = i + 1
}
let heap_keys: ptr<f64> = malloc(((P * 2 + 8) as i64) * 8) as ptr<f64>
let heap_ids: ptr<i32> = malloc(((P * 2 + 8) as i64) * 4) as ptr<i32>
let mut hn: i32 = 0
i = 0
while i < P {
hn = hpush(heap_keys, heap_ids, hn, seg_ends_arr[i][0], i)
i = i + 1
}
let mut cur_pos: f64 = 0.0
let mut best: f64 = total
let eps: f64 = 1e-15
let aff: ptr<i32> = malloc(512 * 4) as ptr<i32>
while hn > 0 {
let boundary: f64 = heap_keys[0]
if boundary > cur_pos + 1e-18 {
if total > best { best = total }
}
let na: i32 = 0
while hn > 0 && fabs(heap_keys[0] - boundary) <= eps {
let out_id: ptr<i32> = calloc(1, 4) as ptr<i32>
hn = hpop(heap_keys, heap_ids, hn, out_id)
if na < 512 {
aff[na] = out_id[0]
na = na + 1
}
free(out_id)
}
cur_pos = boundary
if cur_pos >= domain_end - 1e-15 { break }
let mut a: i32 = 0
while a < na {
let ii: i32 = aff[a]
let old: f64 = cur[ii]
idx[ii] = idx[ii] + 1
let nv: f64 = seg_vals_arr[ii][idx[ii]]
cur[ii] = nv
total = total + nv - old
hn = hpush(heap_keys, heap_ids, hn, seg_ends_arr[ii][idx[ii]], ii)
a = a + 1
}
}
free(idx)
free(cur)
free(heap_keys)
free(heap_ids)
free(aff)
return best
}
function primes_up_to(n: i32, outc: ptr<i32>) -> ptr<i32> {
let sv: ptr<i8> = calloc((n + 1) as i64, 1) as ptr<i8>
let mut i: i32 = 0
while i <= n {
sv[i] = 1
i = i + 1
}
sv[0] = 0
sv[1] = 0
let r: i32 = sqrt((n as f64)) as i32
i = 2
while i <= r {
if sv[i] == 1 {
let mut j: i64 = (i as i64) * (i as i64)
while j <= (n as i64) {
sv[j] = 0
j = j + (i as i64)
}
}
i = i + 1
}
let mut c: i32 = 0
i = 2
while i <= n {
if sv[i] == 1 { c = c + 1 }
i = i + 1
}
let ps: ptr<i32> = malloc((c as i64) * 4) as ptr<i32>
c = 0
i = 2
while i <= n {
if sv[i] == 1 {
ps[c] = i
c = c + 1
}
i = i + 1
}
free(sv)
outc[0] = c
return ps
}
function main() -> i32 {
let n: i32 = 100
let g: f64 = 0.00002
let outc: ptr<i32> = calloc(1, 4) as ptr<i32>
let ps: ptr<i32> = primes_up_to(n, outc)
let npc: i32 = outc[0]
free(outc)
let seg_ends_arr: ptr<ptr<f64> > = calloc(npc as i64, 8) as ptr<ptr<f64> >
let seg_vals_arr: ptr<ptr<f64> > = calloc(npc as i64, 8) as ptr<ptr<f64> >
let seg_n_arr: ptr<i32> = calloc(npc as i64, 4) as ptr<i32>
let mut i: i32 = 0
while i < npc {
let seg: Seg = build_piecewise(1.0 / sqrt((ps[i] as f64)), g)
seg_ends_arr[i] = seg.ends
seg_vals_arr[i] = seg.vals
seg_n_arr[i] = seg.n
i = i + 1
}
let ans: f64 = merge_max_sum(seg_ends_arr, seg_vals_arr, seg_n_arr, npc, 1.0 - g)
i = 0
while i < npc {
free(seg_ends_arr[i])
free(seg_vals_arr[i])
i = i + 1
}
free(seg_ends_arr)
free(seg_vals_arr)
free(seg_n_arr)
free(ps)
printf("%.4f\n", ans)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
typedef struct Seg Seg;
struct Seg {
double* ends;
double* vals;
int32_t n;
};
void sift_down_ptr_f64_i64_i64(double* arr, int64_t start, int64_t end);
void sort_doubles_ptr_f64_i64(double* arr, int64_t n);
int32_t bisect_left_ptr_f64_i32_f64(double* a, int32_t n, double x);
int32_t findp_ptr_i32_i32(int32_t* parent, int32_t i0);
Seg build_piecewise_f64_f64(double l, double g);
int32_t hpush_ptr_f64_ptr_i32_i32_f64_i32(double* heap_keys, int32_t* heap_ids, int32_t hn0, double key, int32_t id);
int32_t hpop_ptr_f64_ptr_i32_i32_ptr_i32(double* heap_keys, int32_t* heap_ids, int32_t hn0, int32_t* out_id);
double merge_max_sum_ptr_ptr_f64_ptr_ptr_f64_ptr_i32_i32_f64(double** seg_ends_arr, double** seg_vals_arr, int32_t* seg_n_arr, int32_t P, double domain_end);
int32_t* primes_up_to_i32_ptr_i32(int32_t n, int32_t* outc);
int32_t main(void);
void sift_down_ptr_f64_i64_i64(double* arr, int64_t start, int64_t end) {
int64_t root = start;
while (((2 * root) + 1) < end) {
int64_t child = ((2 * root) + 1);
if ((child + 1) < end) {
if (arr[child] < arr[(child + 1)]) {
child = (child + 1);
}
}
if (arr[root] < arr[child]) {
double tmp = arr[root];
arr[root] = arr[child];
arr[child] = tmp;
root = child;
} else {
return;
}
}
}
void sort_doubles_ptr_f64_i64(double* arr, int64_t n) {
if (n < 2) {
return;
}
int64_t start = FLOW_CHECKED_DIV((n), (2));
while (start > 0) {
start = (start - 1);
sift_down_ptr_f64_i64_i64(arr, start, n);
}
int64_t end = n;
while (end > 1) {
end = (end - 1);
double tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
sift_down_ptr_f64_i64_i64(arr, 0, end);
}
}
int32_t bisect_left_ptr_f64_i32_f64(double* a, int32_t n, double x) {
int32_t lo = 0;
int32_t hi = n;
while (lo < hi) {
int32_t mid = (lo + FLOW_CHECKED_DIV(((hi - lo)), (2)));
if (a[mid] < x) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
int32_t findp_ptr_i32_i32(int32_t* parent, int32_t i0) {
int32_t i = i0;
while (parent[i] != i) {
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}
Seg build_piecewise_f64_f64(double l, double g) {
double domain_end = (1.0 - g);
int32_t K = ((int32_t)((1.5 / g)));
if (K < 10) {
K = 10;
}
while (1) {
if (K > 4000000) {
return (Seg){ .ends = NULL, .vals = NULL, .n = 0 };
}
double* starts = (double*)(((double*)(malloc((((int64_t)(K)) * 8)))));
double* ends_arr = (double*)(((double*)(malloc((((int64_t)(K)) * 8)))));
int32_t* labels = (int32_t*)(((int32_t*)(malloc((((int64_t)(K)) * 4)))));
int32_t nint = 0;
double* endpoints = (double*)(((double*)(malloc((((int64_t)(((2 * K) + 2))) * 8)))));
int32_t nep = 0;
endpoints[0] = 0.0;
nep = 1;
endpoints[1] = domain_end;
nep = 2;
double x = 0.0;
int32_t k = 1;
while (k <= K) {
x = (x + l);
x = (x - floor(x));
double s = (x - g);
double e = x;
if ((e <= 0.0 || s >= domain_end)) {
k = (k + 1);
continue;
}
double ss = s;
double ee = e;
if (ss < 0.0) {
ss = 0.0;
}
if (ee > domain_end) {
ee = domain_end;
}
if (ss < ee) {
starts[nint] = ss;
ends_arr[nint] = ee;
labels[nint] = k;
endpoints[nep] = ss;
nep = (nep + 1);
endpoints[nep] = ee;
nep = (nep + 1);
nint = (nint + 1);
}
k = (k + 1);
}
sort_doubles_ptr_f64_i64(endpoints, ((int64_t)(nep)));
int32_t nu = 0;
int32_t i = 0;
while (i < nep) {
if ((nu == 0 || endpoints[i] != endpoints[(nu - 1)])) {
endpoints[nu] = endpoints[i];
nu = (nu + 1);
}
i = (i + 1);
}
int32_t num_cells = (nu - 1);
int32_t* parent = (int32_t*)(((int32_t*)(malloc((((int64_t)((num_cells + 1))) * 4)))));
int32_t* values = (int32_t*)(((int32_t*)(calloc(((int64_t)(num_cells)), 4))));
i = 0;
while (i <= num_cells) {
parent[i] = i;
i = (i + 1);
}
int32_t t = 0;
while (t < nint) {
int32_t bi = bisect_left_ptr_f64_i32_f64(endpoints, nu, starts[t]);
int32_t bj = bisect_left_ptr_f64_i32_f64(endpoints, nu, ends_arr[t]);
int32_t idx = findp_ptr_i32_i32(parent, bi);
while (idx < bj) {
values[idx] = labels[t];
parent[idx] = (idx + 1);
idx = findp_ptr_i32_i32(parent, idx);
}
t = (t + 1);
}
if (findp_ptr_i32_i32(parent, 0) == num_cells) {
double* seg_ends = (double*)(((double*)(malloc((((int64_t)((num_cells + 1))) * 8)))));
double* seg_vals = (double*)(((double*)(malloc((((int64_t)((num_cells + 1))) * 8)))));
int32_t seg_n = 0;
int32_t curr = values[0];
i = 1;
while (i < num_cells) {
if (values[i] != curr) {
seg_ends[seg_n] = endpoints[i];
seg_vals[seg_n] = (((double)(curr)) * l);
seg_n = (seg_n + 1);
curr = values[i];
}
i = (i + 1);
}
seg_ends[seg_n] = domain_end;
seg_vals[seg_n] = (((double)(curr)) * l);
seg_n = (seg_n + 1);
free(starts);
free(ends_arr);
free(labels);
free(endpoints);
free(parent);
free(values);
return (Seg){ .ends = seg_ends, .vals = seg_vals, .n = seg_n };
}
free(starts);
free(ends_arr);
free(labels);
free(endpoints);
free(parent);
free(values);
K = (K * 2);
}
return (Seg){ .ends = NULL, .vals = NULL, .n = 0 };
}
int32_t hpush_ptr_f64_ptr_i32_i32_f64_i32(double* heap_keys, int32_t* heap_ids, int32_t hn0, double key, int32_t id) {
int32_t n = hn0;
int32_t i = n;
n = (n + 1);
heap_keys[i] = key;
heap_ids[i] = id;
while (i > 0) {
int32_t p = FLOW_CHECKED_DIV(((i - 1)), (2));
if (heap_keys[p] <= heap_keys[i]) {
break;
}
double tk = heap_keys[p];
int32_t ti = heap_ids[p];
heap_keys[p] = heap_keys[i];
heap_ids[p] = heap_ids[i];
heap_keys[i] = tk;
heap_ids[i] = ti;
i = p;
}
return n;
}
int32_t hpop_ptr_f64_ptr_i32_i32_ptr_i32(double* heap_keys, int32_t* heap_ids, int32_t hn0, int32_t* out_id) {
out_id[0] = heap_ids[0];
int32_t n = (hn0 - 1);
heap_keys[0] = heap_keys[n];
heap_ids[0] = heap_ids[n];
int32_t i = 0;
while (1) {
int32_t l = ((2 * i) + 1);
int32_t rg = ((2 * i) + 2);
int32_t sm = i;
if (l < n) {
if (heap_keys[l] < heap_keys[sm]) {
sm = l;
}
}
if (rg < n) {
if (heap_keys[rg] < heap_keys[sm]) {
sm = rg;
}
}
if (sm == i) {
break;
}
double tk = heap_keys[i];
int32_t ti = heap_ids[i];
heap_keys[i] = heap_keys[sm];
heap_ids[i] = heap_ids[sm];
heap_keys[sm] = tk;
heap_ids[sm] = ti;
i = sm;
}
return n;
}
double merge_max_sum_ptr_ptr_f64_ptr_ptr_f64_ptr_i32_i32_f64(double** seg_ends_arr, double** seg_vals_arr, int32_t* seg_n_arr, int32_t P, double domain_end) {
int32_t* idx = (int32_t*)(((int32_t*)(calloc(((int64_t)(P)), 4))));
double* cur = (double*)(((double*)(malloc((((int64_t)(P)) * 8)))));
double total = 0.0;
int32_t i = 0;
while (i < P) {
cur[i] = seg_vals_arr[i][0];
total = (total + cur[i]);
i = (i + 1);
}
double* heap_keys = (double*)(((double*)(malloc((((int64_t)(((P * 2) + 8))) * 8)))));
int32_t* heap_ids = (int32_t*)(((int32_t*)(malloc((((int64_t)(((P * 2) + 8))) * 4)))));
int32_t hn = 0;
i = 0;
while (i < P) {
hn = hpush_ptr_f64_ptr_i32_i32_f64_i32(heap_keys, heap_ids, hn, seg_ends_arr[i][0], i);
i = (i + 1);
}
double cur_pos = 0.0;
double best = total;
double eps = 1e-15;
int32_t* aff = (int32_t*)(((int32_t*)(malloc((512 * 4)))));
while (hn > 0) {
double boundary = heap_keys[0];
if (boundary > (cur_pos + 1e-18)) {
if (total > best) {
best = total;
}
}
int32_t na = 0;
while ((hn > 0 && fabs((heap_keys[0] - boundary)) <= eps)) {
int32_t* out_id = (int32_t*)(((int32_t*)(calloc(1, 4))));
hn = hpop_ptr_f64_ptr_i32_i32_ptr_i32(heap_keys, heap_ids, hn, out_id);
if (na < 512) {
aff[na] = out_id[0];
na = (na + 1);
}
free(out_id);
}
cur_pos = boundary;
if (cur_pos >= (domain_end - 1e-15)) {
break;
}
int32_t a = 0;
while (a < na) {
int32_t ii = aff[a];
double old = cur[ii];
idx[ii] = (idx[ii] + 1);
double nv = seg_vals_arr[ii][idx[ii]];
cur[ii] = nv;
total = ((total + nv) - old);
hn = hpush_ptr_f64_ptr_i32_i32_f64_i32(heap_keys, heap_ids, hn, seg_ends_arr[ii][idx[ii]], ii);
a = (a + 1);
}
}
free(idx);
free(cur);
free(heap_keys);
free(heap_ids);
free(aff);
return best;
}
int32_t* primes_up_to_i32_ptr_i32(int32_t n, int32_t* outc) {
int8_t* sv = (int8_t*)(((int8_t*)(calloc(((int64_t)((n + 1))), 1))));
int32_t i = 0;
while (i <= n) {
sv[i] = 1;
i = (i + 1);
}
sv[0] = 0;
sv[1] = 0;
int32_t r = ((int32_t)(sqrt(((double)(n)))));
i = 2;
while (i <= r) {
if (sv[i] == 1) {
int64_t j = (((int64_t)(i)) * ((int64_t)(i)));
while (j <= ((int64_t)(n))) {
sv[j] = 0;
j = (j + ((int64_t)(i)));
}
}
i = (i + 1);
}
int32_t c = 0;
i = 2;
while (i <= n) {
if (sv[i] == 1) {
c = (c + 1);
}
i = (i + 1);
}
int32_t* ps = (int32_t*)(((int32_t*)(malloc((((int64_t)(c)) * 4)))));
c = 0;
i = 2;
while (i <= n) {
if (sv[i] == 1) {
ps[c] = i;
c = (c + 1);
}
i = (i + 1);
}
free(sv);
outc[0] = c;
return ps;
}
int32_t main(void) {
int32_t n = 100;
double g = 0.00002;
int32_t* outc = (int32_t*)(((int32_t*)(calloc(1, 4))));
int32_t* ps = (int32_t*)(primes_up_to_i32_ptr_i32(n, outc));
int32_t npc = outc[0];
free(outc);
double** seg_ends_arr = (double**)(((double**)(calloc(((int64_t)(npc)), 8))));
double** seg_vals_arr = (double**)(((double**)(calloc(((int64_t)(npc)), 8))));
int32_t* seg_n_arr = (int32_t*)(((int32_t*)(calloc(((int64_t)(npc)), 4))));
int32_t i = 0;
while (i < npc) {
Seg seg = build_piecewise_f64_f64((1.0 / sqrt(((double)(ps[i])))), g);
seg_ends_arr[i] = seg.ends;
seg_vals_arr[i] = seg.vals;
seg_n_arr[i] = seg.n;
i = (i + 1);
}
double ans = merge_max_sum_ptr_ptr_f64_ptr_ptr_f64_ptr_i32_i32_f64(seg_ends_arr, seg_vals_arr, seg_n_arr, npc, (1.0 - g));
i = 0;
while (i < npc) {
free(seg_ends_arr[i]);
free(seg_vals_arr[i]);
i = (i + 1);
}
free(seg_ends_arr);
free(seg_vals_arr);
free(seg_n_arr);
free(ps);
printf("%.4f\n", ans);
return 0;
}