Problem 328
Sum of minimal worst-case search costs C(n) for n<=200000.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Sieve or enumeration |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 328
# Sum of minimal worst-case search costs C(n) for n<=200000.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function bisect_left_g(G: ptr<i64>, glen: i64, x: i64) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = glen
while lo < hi {
let mid: i64 = (lo + hi) / 2
if G[mid] < x { lo = mid + 1 }
else { hi = mid }
}
return lo
}
function complete_coeff(L: i64, G: ptr<i64>, glen: i64, memo_m: ptr<i64>, memo_c: ptr<i64>, seen: ptr<i8>) -> i64 {
# stores m in memo_m[L], c in memo_c[L]; returns 0
if seen[L] == 1 { return 0 }
if L <= 0 {
memo_m[L] = 0; memo_c[L] = 0; seen[L] = 1; return 0
}
if L == 1 {
memo_m[L] = 1; memo_c[L] = 0; seen[L] = 1; return 0
}
if L == 2 {
memo_m[L] = 1; memo_c[L] = 1; seen[L] = 1; return 0
}
let idx: i64 = bisect_left_g(G, glen, L)
let t: i64 = G[idx - 1]
let mut d: i64 = t
let alt: i64 = L - (t - 1) / 2
if alt < d { d = alt }
let L_left: i64 = d - 1
let L_right: i64 = L - d - 1
complete_coeff(L_left, G, glen, memo_m, memo_c, seen)
complete_coeff(L_right, G, glen, memo_m, memo_c, seen)
let m1: i64 = memo_m[L_left]
let c1: i64 = memo_c[L_left]
let m2: i64 = memo_m[L_right]
let c2: i64 = memo_c[L_right]
let right_const: i64 = c2 + m2 * (d + 1)
let mut m_dom: i64 = m1
let mut c_dom: i64 = c1
if m2 > m1 {
m_dom = m2; c_dom = right_const
} elif m2 == m1 {
if c1 < right_const {
m_dom = m2; c_dom = right_const
}
}
memo_m[L] = m_dom + 1
memo_c[L] = d + c_dom
seen[L] = 1
return 0
}
function complete_cost(lo: i64, hi: i64, G: ptr<i64>, glen: i64, memo_m: ptr<i64>, memo_c: ptr<i64>, seen: ptr<i8>) -> i64 {
let L: i64 = hi - lo
complete_coeff(L, G, glen, memo_m, memo_c, seen)
return memo_m[L] * lo + memo_c[L]
}
function main() -> i32 {
let limit: i64 = 200000
let G: ptr<i64> = calloc(64, 8)
let mut x: i64 = 1
let mut glen: i64 = 0
while x < 400000 {
G[glen] = x
glen = glen + 1
x = x * 2 + 1
}
let memo_m: ptr<i64> = calloc(limit + 2, 8)
let memo_c: ptr<i64> = calloc(limit + 2, 8)
let seen: ptr<i8> = calloc(limit + 2, 1)
let C: ptr<i64> = calloc(limit + 1, 8)
C[1] = 0; C[2] = 1; C[3] = 2; C[4] = 4; C[5] = 6; C[6] = 8
let q: ptr<i64> = calloc(32, 8)
q[0] = 0
let mut qc: i64 = 1
let mut p: i64 = 4
while p <= 131072 {
q[qc] = p
qc = qc + 1
p = p * 2
}
let mut dist: i64 = 3
let mut ii: i64 = 2
let mut running: i64 = 0 + 1 + 2 + 4 + 6 + 8
let mut n: i64 = 7
while n <= limit {
let mut bound: i64 = 1
let mut t: i64 = 0
while t < ii {
bound = bound * 4
t = t + 1
}
if dist > bound { ii = ii + 1 }
let mut best_cost: i64 = -1
let mut best_dist: i64 = -1
let mut qi: i64 = 0
while qi < ii && qi < qc {
let k: i64 = n - dist - q[qi]
if k > 0 && k < n {
let left: i64 = C[k - 1]
let mut right: i64 = 0
if k != n {
right = complete_cost(k + 1, n, G, glen, memo_m, memo_c, seen)
}
let mut worst: i64 = left
if right > worst { worst = right }
let total: i64 = k + worst
let new_dist: i64 = dist + q[qi]
if best_cost < 0 || total < best_cost {
best_cost = total
best_dist = new_dist
}
}
qi = qi + 1
}
C[n] = best_cost
dist = best_dist
running = running + best_cost
n = n + 1
}
printf("%lld\n", running)
free(G); free(memo_m); free(memo_c); free(seen); free(C); free(q)
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; }
int64_t bisect_left_g_ptr_i64_i64_i64(int64_t* G, int64_t glen, int64_t x);
int64_t complete_coeff_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(int64_t L, int64_t* G, int64_t glen, int64_t* memo_m, int64_t* memo_c, int8_t* seen);
int64_t complete_cost_i64_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(int64_t lo, int64_t hi, int64_t* G, int64_t glen, int64_t* memo_m, int64_t* memo_c, int8_t* seen);
int32_t main(void);
int64_t bisect_left_g_ptr_i64_i64_i64(int64_t* G, int64_t glen, int64_t x) {
int64_t lo = 0;
int64_t hi = glen;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (G[mid] < x) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
int64_t complete_coeff_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(int64_t L, int64_t* G, int64_t glen, int64_t* memo_m, int64_t* memo_c, int8_t* seen) {
if (seen[L] == 1) {
return 0;
}
if (L <= 0) {
memo_m[L] = 0;
memo_c[L] = 0;
seen[L] = 1;
return 0;
}
if (L == 1) {
memo_m[L] = 1;
memo_c[L] = 0;
seen[L] = 1;
return 0;
}
if (L == 2) {
memo_m[L] = 1;
memo_c[L] = 1;
seen[L] = 1;
return 0;
}
int64_t idx = bisect_left_g_ptr_i64_i64_i64(G, glen, L);
int64_t t = G[(idx - 1)];
int64_t d = t;
int64_t alt = (L - FLOW_CHECKED_DIV(((t - 1)), (2)));
if (alt < d) {
d = alt;
}
int64_t L_left = (d - 1);
int64_t L_right = ((L - d) - 1);
complete_coeff_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(L_left, G, glen, memo_m, memo_c, seen);
complete_coeff_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(L_right, G, glen, memo_m, memo_c, seen);
int64_t m1 = memo_m[L_left];
int64_t c1 = memo_c[L_left];
int64_t m2 = memo_m[L_right];
int64_t c2 = memo_c[L_right];
int64_t right_const = (c2 + (m2 * (d + 1)));
int64_t m_dom = m1;
int64_t c_dom = c1;
if (m2 > m1) {
m_dom = m2;
c_dom = right_const;
} else if (m2 == m1) {
if (c1 < right_const) {
m_dom = m2;
c_dom = right_const;
}
}
memo_m[L] = (m_dom + 1);
memo_c[L] = (d + c_dom);
seen[L] = 1;
return 0;
}
int64_t complete_cost_i64_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(int64_t lo, int64_t hi, int64_t* G, int64_t glen, int64_t* memo_m, int64_t* memo_c, int8_t* seen) {
int64_t L = (hi - lo);
complete_coeff_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8(L, G, glen, memo_m, memo_c, seen);
return ((memo_m[L] * lo) + memo_c[L]);
}
int32_t main(void) {
int64_t limit = 200000;
int64_t* G = (int64_t*)(calloc(64, 8));
int64_t x = 1;
int64_t glen = 0;
while (x < 400000) {
G[glen] = x;
glen = (glen + 1);
x = ((x * 2) + 1);
}
int64_t* memo_m = (int64_t*)(calloc((limit + 2), 8));
int64_t* memo_c = (int64_t*)(calloc((limit + 2), 8));
int8_t* seen = (int8_t*)(calloc((limit + 2), 1));
int64_t* C = (int64_t*)(calloc((limit + 1), 8));
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 4;
C[5] = 6;
C[6] = 8;
int64_t* q = (int64_t*)(calloc(32, 8));
q[0] = 0;
int64_t qc = 1;
int64_t p = 4;
while (p <= 131072) {
q[qc] = p;
qc = (qc + 1);
p = (p * 2);
}
int64_t dist = 3;
int64_t ii = 2;
int64_t running = (((((0 + 1) + 2) + 4) + 6) + 8);
int64_t n = 7;
while (n <= limit) {
int64_t bound = 1;
int64_t t = 0;
while (t < ii) {
bound = (bound * 4);
t = (t + 1);
}
if (dist > bound) {
ii = (ii + 1);
}
int64_t best_cost = (-1);
int64_t best_dist = (-1);
int64_t qi = 0;
while ((qi < ii && qi < qc)) {
int64_t k = ((n - dist) - q[qi]);
if ((k > 0 && k < n)) {
int64_t left = C[(k - 1)];
int64_t right = 0;
if (k != n) {
right = complete_cost_i64_i64_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i8((k + 1), n, G, glen, memo_m, memo_c, seen);
}
int64_t worst = left;
if (right > worst) {
worst = right;
}
int64_t total = (k + worst);
int64_t new_dist = (dist + q[qi]);
if ((best_cost < 0 || total < best_cost)) {
best_cost = total;
best_dist = new_dist;
}
}
qi = (qi + 1);
}
C[n] = best_cost;
dist = best_dist;
running = (running + best_cost);
n = (n + 1);
}
printf("%lld\n", running);
free(G);
free(memo_m);
free(memo_c);
free(seen);
free(C);
free(q);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @bisect_left_g(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 0 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = llvm.mlir.constant(1 : i64) : i64
%5 = llvm.alloca %4 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %5 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%6 = llvm.load %3 : !llvm.ptr -> i64
%7 = llvm.load %5 : !llvm.ptr -> i64
%8 = arith.cmpi slt, %6, %7 : i64
cf.cond_br %8, ^bb1, ^bb2
^bb1:
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = llvm.load %5 : !llvm.ptr -> i64
%11 = arith.addi %9, %10 : i64
%12 = arith.constant 2 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.divsi %11, %14 : i64
%16 = llvm.getelementptr %arg0[%13] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%15 = llvm.load %16 : !llvm.ptr -> i64
%17 = arith.cmpi slt, %15, %arg2 : i64
cf.cond_br %17, ^bb3, ^bb4
^bb3:
%18 = arith.constant 1 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.addi %13, %20 : i64
llvm.store %19, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
llvm.store %13, %5 : i64, !llvm.ptr
cf.br ^bb5
^bb5:
cf.br ^bb0
^bb2:
%21 = llvm.load %3 : !llvm.ptr -> i64
func.return %21 : i64
}
func.func @complete_coeff(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr) -> i64 {
%23 = llvm.getelementptr %arg5[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%22 = llvm.load %23 : !llvm.ptr -> i8
%24 = arith.constant 1 : i32
%26 = arith.extsi %22 : i8 to i32
%25 = arith.cmpi eq, %26, %24 : i32
cf.cond_br %25, ^bb6, ^bb7
^bb6:
%27 = arith.constant 0 : i32
%28 = arith.extsi %27 : i32 to i64
func.return %28 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = arith.constant 0 : i32
%31 = arith.extsi %29 : i32 to i64
%30 = arith.cmpi sle, %arg0, %31 : i64
cf.cond_br %30, ^bb9, ^bb10
^bb9:
%32 = arith.constant 0 : i32
%33 = arith.extsi %32 : i32 to i64
%34 = llvm.getelementptr %arg3[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %33, %34 : i64, !llvm.ptr
%35 = arith.constant 0 : i32
%36 = arith.extsi %35 : i32 to i64
%37 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %36, %37 : i64, !llvm.ptr
%38 = arith.constant 1 : i32
%39 = arith.trunci %38 : i32 to i8
%40 = llvm.getelementptr %arg5[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %39, %40 : i8, !llvm.ptr
%41 = arith.constant 0 : i32
%42 = arith.extsi %41 : i32 to i64
func.return %42 : i64
^bb10:
cf.br ^bb11
^bb11:
%43 = arith.constant 1 : i32
%45 = arith.extsi %43 : i32 to i64
%44 = arith.cmpi eq, %arg0, %45 : i64
cf.cond_br %44, ^bb12, ^bb13
^bb12:
%46 = arith.constant 1 : i32
%47 = arith.extsi %46 : i32 to i64
%48 = llvm.getelementptr %arg3[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %47, %48 : i64, !llvm.ptr
%49 = arith.constant 0 : i32
%50 = arith.extsi %49 : i32 to i64
%51 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %50, %51 : i64, !llvm.ptr
%52 = arith.constant 1 : i32
%53 = arith.trunci %52 : i32 to i8
%54 = llvm.getelementptr %arg5[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %53, %54 : i8, !llvm.ptr
%55 = arith.constant 0 : i32
%56 = arith.extsi %55 : i32 to i64
func.return %56 : i64
^bb13:
cf.br ^bb14
^bb14:
%57 = arith.constant 2 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.cmpi eq, %arg0, %59 : i64
cf.cond_br %58, ^bb15, ^bb16
^bb15:
%60 = arith.constant 1 : i32
%61 = arith.extsi %60 : i32 to i64
%62 = llvm.getelementptr %arg3[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %61, %62 : i64, !llvm.ptr
%63 = arith.constant 1 : i32
%64 = arith.extsi %63 : i32 to i64
%65 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %64, %65 : i64, !llvm.ptr
%66 = arith.constant 1 : i32
%67 = arith.trunci %66 : i32 to i8
%68 = llvm.getelementptr %arg5[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %67, %68 : i8, !llvm.ptr
%69 = arith.constant 0 : i32
%70 = arith.extsi %69 : i32 to i64
func.return %70 : i64
^bb16:
cf.br ^bb17
^bb17:
%71 = func.call @bisect_left_g(%arg1, %arg2, %arg0) : (!llvm.ptr, i64, i64) -> i64
%73 = arith.constant 1 : i32
%75 = arith.extsi %73 : i32 to i64
%74 = arith.subi %71, %75 : i64
%76 = llvm.getelementptr %arg1[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%72 = llvm.load %76 : !llvm.ptr -> i64
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i64 : (i64) -> !llvm.ptr
llvm.store %72, %78 : i64, !llvm.ptr
%79 = arith.constant 1 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.subi %72, %81 : i64
%82 = arith.constant 2 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.divsi %80, %84 : i64
%85 = arith.subi %arg0, %83 : i64
%86 = llvm.load %78 : !llvm.ptr -> i64
%87 = arith.cmpi slt, %85, %86 : i64
cf.cond_br %87, ^bb18, ^bb19
^bb18:
llvm.store %85, %78 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%88 = llvm.load %78 : !llvm.ptr -> i64
%89 = arith.constant 1 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.subi %88, %91 : i64
%92 = llvm.load %78 : !llvm.ptr -> i64
%93 = arith.subi %arg0, %92 : i64
%94 = arith.constant 1 : i32
%96 = arith.extsi %94 : i32 to i64
%95 = arith.subi %93, %96 : i64
%97 = func.call @complete_coeff(%90, %arg1, %arg2, %arg3, %arg4, %arg5) : (i64, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%98 = func.call @complete_coeff(%95, %arg1, %arg2, %arg3, %arg4, %arg5) : (i64, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%100 = llvm.getelementptr %arg3[%90] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%99 = llvm.load %100 : !llvm.ptr -> i64
%102 = llvm.getelementptr %arg4[%90] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%101 = llvm.load %102 : !llvm.ptr -> i64
%104 = llvm.getelementptr %arg3[%95] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%103 = llvm.load %104 : !llvm.ptr -> i64
%106 = llvm.getelementptr %arg4[%95] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%105 = llvm.load %106 : !llvm.ptr -> i64
%107 = llvm.load %78 : !llvm.ptr -> i64
%108 = arith.constant 1 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.addi %107, %110 : i64
%111 = arith.muli %103, %109 : i64
%112 = arith.addi %105, %111 : i64
%113 = llvm.mlir.constant(1 : i64) : i64
%114 = llvm.alloca %113 x i64 : (i64) -> !llvm.ptr
llvm.store %99, %114 : i64, !llvm.ptr
%115 = llvm.mlir.constant(1 : i64) : i64
%116 = llvm.alloca %115 x i64 : (i64) -> !llvm.ptr
llvm.store %101, %116 : i64, !llvm.ptr
%117 = arith.cmpi sgt, %103, %99 : i64
cf.cond_br %117, ^bb21, ^bb22
^bb21:
llvm.store %103, %114 : i64, !llvm.ptr
llvm.store %112, %116 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
%118 = arith.cmpi eq, %103, %99 : i64
cf.cond_br %118, ^bb24, ^bb23
^bb24:
%119 = arith.cmpi slt, %101, %112 : i64
cf.cond_br %119, ^bb25, ^bb26
^bb25:
llvm.store %103, %114 : i64, !llvm.ptr
llvm.store %112, %116 : i64, !llvm.ptr
cf.br ^bb27
^bb26:
cf.br ^bb27
^bb27:
cf.br ^bb23
^bb23:
%120 = llvm.load %114 : !llvm.ptr -> i64
%121 = arith.constant 1 : i32
%123 = arith.extsi %121 : i32 to i64
%122 = arith.addi %120, %123 : i64
%124 = llvm.getelementptr %arg3[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %122, %124 : i64, !llvm.ptr
%125 = llvm.load %78 : !llvm.ptr -> i64
%126 = llvm.load %116 : !llvm.ptr -> i64
%127 = arith.addi %125, %126 : i64
%128 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %127, %128 : i64, !llvm.ptr
%129 = arith.constant 1 : i32
%130 = arith.trunci %129 : i32 to i8
%131 = llvm.getelementptr %arg5[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %130, %131 : i8, !llvm.ptr
%132 = arith.constant 0 : i32
%133 = arith.extsi %132 : i32 to i64
func.return %133 : i64
}
func.func @complete_cost(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: i64, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr) -> i64 {
%134 = arith.subi %arg1, %arg0 : i64
%135 = func.call @complete_coeff(%134, %arg2, %arg3, %arg4, %arg5, %arg6) : (i64, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
%137 = llvm.getelementptr %arg4[%134] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%136 = llvm.load %137 : !llvm.ptr -> i64
%138 = arith.muli %136, %arg0 : i64
%140 = llvm.getelementptr %arg5[%134] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%139 = llvm.load %140 : !llvm.ptr -> i64
%141 = arith.addi %138, %139 : i64
func.return %141 : i64
}
func.func @main() -> i32 {
%142 = arith.constant 200000 : i32
%143 = arith.extsi %142 : i32 to i64
%145 = arith.constant 64 : i32
%146 = arith.constant 8 : i32
%147 = arith.extsi %145 : i32 to i64
%148 = arith.extsi %146 : i32 to i64
%144 = func.call @calloc(%147, %148) : (i64, i64) -> !llvm.ptr
%149 = arith.constant 1 : i32
%150 = arith.extsi %149 : i32 to i64
%151 = llvm.mlir.constant(1 : i64) : i64
%152 = llvm.alloca %151 x i64 : (i64) -> !llvm.ptr
llvm.store %150, %152 : i64, !llvm.ptr
%153 = arith.constant 0 : i32
%154 = arith.extsi %153 : i32 to i64
%155 = llvm.mlir.constant(1 : i64) : i64
%156 = llvm.alloca %155 x i64 : (i64) -> !llvm.ptr
llvm.store %154, %156 : i64, !llvm.ptr
cf.br ^bb28
^bb28:
%157 = llvm.load %152 : !llvm.ptr -> i64
%158 = arith.constant 400000 : i32
%160 = arith.extsi %158 : i32 to i64
%159 = arith.cmpi slt, %157, %160 : i64
cf.cond_br %159, ^bb29, ^bb30
^bb29:
%161 = llvm.load %152 : !llvm.ptr -> i64
%162 = llvm.load %156 : !llvm.ptr -> i64
%163 = llvm.getelementptr %144[%162] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %161, %163 : i64, !llvm.ptr
%164 = llvm.load %156 : !llvm.ptr -> i64
%165 = arith.constant 1 : i32
%167 = arith.extsi %165 : i32 to i64
%166 = arith.addi %164, %167 : i64
llvm.store %166, %156 : i64, !llvm.ptr
%168 = llvm.load %152 : !llvm.ptr -> i64
%169 = arith.constant 2 : i32
%171 = arith.extsi %169 : i32 to i64
%170 = arith.muli %168, %171 : i64
%172 = arith.constant 1 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.addi %170, %174 : i64
llvm.store %173, %152 : i64, !llvm.ptr
cf.br ^bb28
^bb30:
%176 = arith.constant 2 : i32
%178 = arith.extsi %176 : i32 to i64
%177 = arith.addi %143, %178 : i64
%179 = arith.constant 8 : i32
%180 = arith.extsi %179 : i32 to i64
%175 = func.call @calloc(%177, %180) : (i64, i64) -> !llvm.ptr
%182 = arith.constant 2 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.addi %143, %184 : i64
%185 = arith.constant 8 : i32
%186 = arith.extsi %185 : i32 to i64
%181 = func.call @calloc(%183, %186) : (i64, i64) -> !llvm.ptr
%188 = arith.constant 2 : i32
%190 = arith.extsi %188 : i32 to i64
%189 = arith.addi %143, %190 : i64
%191 = arith.constant 1 : i32
%192 = arith.extsi %191 : i32 to i64
%187 = func.call @calloc(%189, %192) : (i64, i64) -> !llvm.ptr
%194 = arith.constant 1 : i32
%196 = arith.extsi %194 : i32 to i64
%195 = arith.addi %143, %196 : i64
%197 = arith.constant 8 : i32
%198 = arith.extsi %197 : i32 to i64
%193 = func.call @calloc(%195, %198) : (i64, i64) -> !llvm.ptr
%199 = arith.constant 0 : i32
%200 = arith.constant 1 : i32
%201 = arith.extsi %199 : i32 to i64
%202 = arith.extsi %200 : i32 to i64
%203 = llvm.getelementptr %193[%202] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %201, %203 : i64, !llvm.ptr
%204 = arith.constant 1 : i32
%205 = arith.constant 2 : i32
%206 = arith.extsi %204 : i32 to i64
%207 = arith.extsi %205 : i32 to i64
%208 = llvm.getelementptr %193[%207] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %206, %208 : i64, !llvm.ptr
%209 = arith.constant 2 : i32
%210 = arith.constant 3 : i32
%211 = arith.extsi %209 : i32 to i64
%212 = arith.extsi %210 : i32 to i64
%213 = llvm.getelementptr %193[%212] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %211, %213 : i64, !llvm.ptr
%214 = arith.constant 4 : i32
%215 = arith.constant 4 : i32
%216 = arith.extsi %214 : i32 to i64
%217 = arith.extsi %215 : i32 to i64
%218 = llvm.getelementptr %193[%217] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %216, %218 : i64, !llvm.ptr
%219 = arith.constant 6 : i32
%220 = arith.constant 5 : i32
%221 = arith.extsi %219 : i32 to i64
%222 = arith.extsi %220 : i32 to i64
%223 = llvm.getelementptr %193[%222] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %221, %223 : i64, !llvm.ptr
%224 = arith.constant 8 : i32
%225 = arith.constant 6 : i32
%226 = arith.extsi %224 : i32 to i64
%227 = arith.extsi %225 : i32 to i64
%228 = llvm.getelementptr %193[%227] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %226, %228 : i64, !llvm.ptr
%230 = arith.constant 32 : i32
%231 = arith.constant 8 : i32
%232 = arith.extsi %230 : i32 to i64
%233 = arith.extsi %231 : i32 to i64
%229 = func.call @calloc(%232, %233) : (i64, i64) -> !llvm.ptr
%234 = arith.constant 0 : i32
%235 = arith.constant 0 : i32
%236 = arith.extsi %234 : i32 to i64
%237 = arith.extsi %235 : i32 to i64
%238 = llvm.getelementptr %229[%237] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %236, %238 : i64, !llvm.ptr
%239 = arith.constant 1 : i32
%240 = arith.extsi %239 : i32 to i64
%241 = llvm.mlir.constant(1 : i64) : i64
%242 = llvm.alloca %241 x i64 : (i64) -> !llvm.ptr
llvm.store %240, %242 : i64, !llvm.ptr
%243 = arith.constant 4 : i32
%244 = arith.extsi %243 : i32 to i64
%245 = llvm.mlir.constant(1 : i64) : i64
%246 = llvm.alloca %245 x i64 : (i64) -> !llvm.ptr
llvm.store %244, %246 : i64, !llvm.ptr
cf.br ^bb31
^bb31:
%247 = llvm.load %246 : !llvm.ptr -> i64
%248 = arith.constant 131072 : i32
%250 = arith.extsi %248 : i32 to i64
%249 = arith.cmpi sle, %247, %250 : i64
cf.cond_br %249, ^bb32, ^bb33
^bb32:
%251 = llvm.load %246 : !llvm.ptr -> i64
%252 = llvm.load %242 : !llvm.ptr -> i64
%253 = llvm.getelementptr %229[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %251, %253 : i64, !llvm.ptr
%254 = llvm.load %242 : !llvm.ptr -> i64
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.addi %254, %257 : i64
llvm.store %256, %242 : i64, !llvm.ptr
%258 = llvm.load %246 : !llvm.ptr -> i64
%259 = arith.constant 2 : i32
%261 = arith.extsi %259 : i32 to i64
%260 = arith.muli %258, %261 : i64
llvm.store %260, %246 : i64, !llvm.ptr
cf.br ^bb31
^bb33:
%262 = arith.constant 3 : i32
%263 = arith.extsi %262 : i32 to i64
%264 = llvm.mlir.constant(1 : i64) : i64
%265 = llvm.alloca %264 x i64 : (i64) -> !llvm.ptr
llvm.store %263, %265 : i64, !llvm.ptr
%266 = arith.constant 2 : i32
%267 = arith.extsi %266 : i32 to i64
%268 = llvm.mlir.constant(1 : i64) : i64
%269 = llvm.alloca %268 x i64 : (i64) -> !llvm.ptr
llvm.store %267, %269 : i64, !llvm.ptr
%270 = arith.constant 0 : i32
%271 = arith.constant 1 : i32
%272 = arith.addi %270, %271 : i32
%273 = arith.constant 2 : i32
%274 = arith.addi %272, %273 : i32
%275 = arith.constant 4 : i32
%276 = arith.addi %274, %275 : i32
%277 = arith.constant 6 : i32
%278 = arith.addi %276, %277 : i32
%279 = arith.constant 8 : i32
%280 = arith.addi %278, %279 : i32
%281 = arith.extsi %280 : i32 to i64
%282 = llvm.mlir.constant(1 : i64) : i64
%283 = llvm.alloca %282 x i64 : (i64) -> !llvm.ptr
llvm.store %281, %283 : i64, !llvm.ptr
%284 = arith.constant 7 : i32
%285 = arith.extsi %284 : i32 to i64
%286 = llvm.mlir.constant(1 : i64) : i64
%287 = llvm.alloca %286 x i64 : (i64) -> !llvm.ptr
llvm.store %285, %287 : i64, !llvm.ptr
cf.br ^bb34
^bb34:
%288 = llvm.load %287 : !llvm.ptr -> i64
%289 = arith.cmpi sle, %288, %143 : i64
cf.cond_br %289, ^bb35, ^bb36
^bb35:
%290 = arith.constant 1 : i32
%291 = arith.extsi %290 : i32 to i64
%292 = llvm.mlir.constant(1 : i64) : i64
%293 = llvm.alloca %292 x i64 : (i64) -> !llvm.ptr
llvm.store %291, %293 : i64, !llvm.ptr
%294 = arith.constant 0 : i32
%295 = arith.extsi %294 : i32 to i64
%296 = llvm.mlir.constant(1 : i64) : i64
%297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
llvm.store %295, %297 : i64, !llvm.ptr
cf.br ^bb37
^bb37:
%298 = llvm.load %297 : !llvm.ptr -> i64
%299 = llvm.load %269 : !llvm.ptr -> i64
%300 = arith.cmpi slt, %298, %299 : i64
cf.cond_br %300, ^bb38, ^bb39
^bb38:
%301 = llvm.load %293 : !llvm.ptr -> i64
%302 = arith.constant 4 : i32
%304 = arith.extsi %302 : i32 to i64
%303 = arith.muli %301, %304 : i64
llvm.store %303, %293 : i64, !llvm.ptr
%305 = llvm.load %297 : !llvm.ptr -> i64
%306 = arith.constant 1 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.addi %305, %308 : i64
llvm.store %307, %297 : i64, !llvm.ptr
cf.br ^bb37
^bb39:
%309 = llvm.load %265 : !llvm.ptr -> i64
%310 = llvm.load %293 : !llvm.ptr -> i64
%311 = arith.cmpi sgt, %309, %310 : i64
cf.cond_br %311, ^bb40, ^bb41
^bb40:
%312 = llvm.load %269 : !llvm.ptr -> i64
%313 = arith.constant 1 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.addi %312, %315 : i64
llvm.store %314, %269 : i64, !llvm.ptr
cf.br ^bb42
^bb41:
cf.br ^bb42
^bb42:
%316 = arith.constant 1 : i32
%318 = arith.constant 0 : i32
%317 = arith.subi %318, %316 : i32
%319 = arith.extsi %317 : i32 to i64
%320 = llvm.mlir.constant(1 : i64) : i64
%321 = llvm.alloca %320 x i64 : (i64) -> !llvm.ptr
llvm.store %319, %321 : i64, !llvm.ptr
%322 = arith.constant 1 : i32
%324 = arith.constant 0 : i32
%323 = arith.subi %324, %322 : i32
%325 = arith.extsi %323 : i32 to i64
%326 = llvm.mlir.constant(1 : i64) : i64
%327 = llvm.alloca %326 x i64 : (i64) -> !llvm.ptr
llvm.store %325, %327 : i64, !llvm.ptr
%328 = arith.constant 0 : i32
%329 = arith.extsi %328 : i32 to i64
%330 = llvm.mlir.constant(1 : i64) : i64
%331 = llvm.alloca %330 x i64 : (i64) -> !llvm.ptr
llvm.store %329, %331 : i64, !llvm.ptr
cf.br ^bb43
^bb43:
%332 = llvm.load %331 : !llvm.ptr -> i64
%333 = llvm.load %269 : !llvm.ptr -> i64
%334 = arith.cmpi slt, %332, %333 : i64
%335 = scf.if %334 -> (i1) {
%336 = llvm.load %331 : !llvm.ptr -> i64
%337 = llvm.load %242 : !llvm.ptr -> i64
%338 = arith.cmpi slt, %336, %337 : i64
scf.yield %338 : i1
} else {
%339 = arith.constant false
scf.yield %339 : i1
}
cf.cond_br %335, ^bb44, ^bb45
^bb44:
%340 = llvm.load %287 : !llvm.ptr -> i64
%341 = llvm.load %265 : !llvm.ptr -> i64
%342 = arith.subi %340, %341 : i64
%344 = llvm.load %331 : !llvm.ptr -> i64
%345 = llvm.getelementptr %229[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%343 = llvm.load %345 : !llvm.ptr -> i64
%346 = arith.subi %342, %343 : i64
%347 = arith.constant 0 : i32
%349 = arith.extsi %347 : i32 to i64
%348 = arith.cmpi sgt, %346, %349 : i64
%350 = scf.if %348 -> (i1) {
%351 = llvm.load %287 : !llvm.ptr -> i64
%352 = arith.cmpi slt, %346, %351 : i64
scf.yield %352 : i1
} else {
%353 = arith.constant false
scf.yield %353 : i1
}
cf.cond_br %350, ^bb46, ^bb47
^bb46:
%355 = arith.constant 1 : i32
%357 = arith.extsi %355 : i32 to i64
%356 = arith.subi %346, %357 : i64
%358 = llvm.getelementptr %193[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%354 = llvm.load %358 : !llvm.ptr -> i64
%359 = arith.constant 0 : i32
%360 = arith.extsi %359 : i32 to i64
%361 = llvm.mlir.constant(1 : i64) : i64
%362 = llvm.alloca %361 x i64 : (i64) -> !llvm.ptr
llvm.store %360, %362 : i64, !llvm.ptr
%363 = llvm.load %287 : !llvm.ptr -> i64
%364 = arith.cmpi ne, %346, %363 : i64
cf.cond_br %364, ^bb49, ^bb50
^bb49:
%366 = arith.constant 1 : i32
%368 = arith.extsi %366 : i32 to i64
%367 = arith.addi %346, %368 : i64
%369 = llvm.load %287 : !llvm.ptr -> i64
%370 = llvm.load %156 : !llvm.ptr -> i64
%365 = func.call @complete_cost(%367, %369, %144, %370, %175, %181, %187) : (i64, i64, !llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i64
llvm.store %365, %362 : i64, !llvm.ptr
cf.br ^bb51
^bb50:
cf.br ^bb51
^bb51:
%371 = llvm.mlir.constant(1 : i64) : i64
%372 = llvm.alloca %371 x i64 : (i64) -> !llvm.ptr
llvm.store %354, %372 : i64, !llvm.ptr
%373 = llvm.load %362 : !llvm.ptr -> i64
%374 = llvm.load %372 : !llvm.ptr -> i64
%375 = arith.cmpi sgt, %373, %374 : i64
cf.cond_br %375, ^bb52, ^bb53
^bb52:
%376 = llvm.load %362 : !llvm.ptr -> i64
llvm.store %376, %372 : i64, !llvm.ptr
cf.br ^bb54
^bb53:
cf.br ^bb54
^bb54:
%377 = llvm.load %372 : !llvm.ptr -> i64
%378 = arith.addi %346, %377 : i64
%379 = llvm.load %265 : !llvm.ptr -> i64
%381 = llvm.load %331 : !llvm.ptr -> i64
%382 = llvm.getelementptr %229[%381] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%380 = llvm.load %382 : !llvm.ptr -> i64
%383 = arith.addi %379, %380 : i64
%384 = llvm.load %321 : !llvm.ptr -> i64
%385 = arith.constant 0 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.cmpi slt, %384, %387 : i64
%388 = scf.if %386 -> (i1) {
%389 = arith.constant true
scf.yield %389 : i1
} else {
%390 = llvm.load %321 : !llvm.ptr -> i64
%391 = arith.cmpi slt, %378, %390 : i64
scf.yield %391 : i1
}
cf.cond_br %388, ^bb55, ^bb56
^bb55:
llvm.store %378, %321 : i64, !llvm.ptr
llvm.store %383, %327 : i64, !llvm.ptr
cf.br ^bb57
^bb56:
cf.br ^bb57
^bb57:
cf.br ^bb48
^bb47:
cf.br ^bb48
^bb48:
%392 = llvm.load %331 : !llvm.ptr -> i64
%393 = arith.constant 1 : i32
%395 = arith.extsi %393 : i32 to i64
%394 = arith.addi %392, %395 : i64
llvm.store %394, %331 : i64, !llvm.ptr
cf.br ^bb43
^bb45:
%396 = llvm.load %321 : !llvm.ptr -> i64
%397 = llvm.load %287 : !llvm.ptr -> i64
%398 = llvm.getelementptr %193[%397] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %396, %398 : i64, !llvm.ptr
%399 = llvm.load %327 : !llvm.ptr -> i64
llvm.store %399, %265 : i64, !llvm.ptr
%400 = llvm.load %283 : !llvm.ptr -> i64
%401 = llvm.load %321 : !llvm.ptr -> i64
%402 = arith.addi %400, %401 : i64
llvm.store %402, %283 : i64, !llvm.ptr
%403 = llvm.load %287 : !llvm.ptr -> i64
%404 = arith.constant 1 : i32
%406 = arith.extsi %404 : i32 to i64
%405 = arith.addi %403, %406 : i64
llvm.store %405, %287 : i64, !llvm.ptr
cf.br ^bb34
^bb36:
%407 = llvm.mlir.addressof @str_0 : !llvm.ptr
%408 = llvm.load %283 : !llvm.ptr -> i64
%409 = llvm.call @printf(%407, %408) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%144) : (!llvm.ptr) -> ()
func.call @free(%175) : (!llvm.ptr) -> ()
func.call @free(%181) : (!llvm.ptr) -> ()
func.call @free(%187) : (!llvm.ptr) -> ()
func.call @free(%193) : (!llvm.ptr) -> ()
func.call @free(%229) : (!llvm.ptr) -> ()
%416 = arith.constant 0 : i32
func.return %416 : i32
}
}