Problem 563
Robot Walks Sum of minimal areas with exactly k rectangular tilings for k=2..100.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n * s) |
|---|
| Space complexity | O(n^2) | O(s) |
|---|
| Approach | Flow solution | Tiling DP with state |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 563
# Robot Walks
# Sum of minimal areas with exactly k rectangular tilings for k=2..100.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function realloc(p: ptr<void>, size: i64) -> ptr<void>
}
const IGNORE: i64 = 2300000000000000
const MAX_COMB: i64 = 100
let mut HEAP: ptr<i64> = null
let mut HLEN: i64 = 0
let mut HCAP: i64 = 0
function heap_push(v: i64) -> void {
if HLEN + 1 >= HCAP {
if HCAP == 0 { HCAP = 1024 } else { HCAP = HCAP * 2 }
HEAP = realloc(HEAP, HCAP * 8)
}
let mut i: i64 = HLEN
HLEN = HLEN + 1
HEAP[i] = v
while i > 0 {
let p: i64 = (i - 1) / 2
if HEAP[p] <= HEAP[i] { break }
let t: i64 = HEAP[p]
HEAP[p] = HEAP[i]
HEAP[i] = t
i = p
}
}
function heap_pop() -> i64 {
let res: i64 = HEAP[0]
HLEN = HLEN - 1
HEAP[0] = HEAP[HLEN]
let mut i: i64 = 0
while true {
let l: i64 = 2 * i + 1
let r: i64 = l + 1
let mut smallest: i64 = i
if l < HLEN && HEAP[l] < HEAP[smallest] { smallest = l }
if r < HLEN && HEAP[r] < HEAP[smallest] { smallest = r }
if smallest == i { break }
let t: i64 = HEAP[i]
HEAP[i] = HEAP[smallest]
HEAP[smallest] = t
i = smallest
}
return res
}
function isqrt(n: i64) -> i64 {
if n <= 0 { return 0 }
let mut x: i64 = n
let mut y: i64 = (x + 1) / 2
while y < x {
x = y
y = (x + n / x) / 2
}
return x
}
function bisect_right(sides: ptr<i64>, n: i64, x: i64) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = n
while lo < hi {
let mid: i64 = (lo + hi) / 2
if sides[mid] <= x { lo = mid + 1 } else { hi = mid }
}
return lo
}
function solve() -> i64 {
let solutions: ptr<i64> = calloc(MAX_COMB + 1, 8)
if solutions == null { return -1 }
let mut num_solutions: i64 = 1
let mut result: i64 = 0
HCAP = 4096
HEAP = calloc(HCAP, 8)
HLEN = 0
heap_push(1)
let mut sides_cap: i64 = 200000
let mut sides: ptr<i64> = calloc(sides_cap, 8)
let mut sides_len: i64 = 0
if sides == null { return -1 }
let multiples: ptr<i64> = calloc(9, 8)
multiples[0] = 23
multiples[1] = 19
multiples[2] = 17
multiples[3] = 13
multiples[4] = 11
multiples[5] = 7
multiples[6] = 5
multiples[7] = 3
multiples[8] = 2
while num_solutions < MAX_COMB {
let current: i64 = heap_pop()
if current * current <= IGNORE {
if sides_len + 1 >= sides_cap {
sides_cap = sides_cap * 2
sides = realloc(sides, sides_cap * 8)
}
sides[sides_len] = current
sides_len = sides_len + 1
}
let mut mi: i64 = 0
while mi < 9 {
let multiple: i64 = multiples[mi]
let next_value: i64 = multiple * current
if next_value <= IGNORE {
heap_push(next_value)
}
if current % multiple == 0 { break }
mi = mi + 1
}
if num_solutions >= 56 {
if current % 800 != 0 { continue }
} elif num_solutions >= 8 {
if current % 80 != 0 { continue }
} elif current % 40 != 0 {
continue
}
let mut idx: i64 = bisect_right(sides, sides_len, isqrt(current)) - 1
if idx <= 0 { continue }
let mut num_found: i64 = 0
while idx > 0 {
let short_side: i64 = sides[idx]
idx = idx - 1
let long_side: i64 = current / short_side
if long_side * 10 > short_side * 11 { break }
if long_side * short_side == current {
num_found = num_found + 1
}
}
if num_found < 2 || num_found > MAX_COMB { continue }
if solutions[num_found] == 0 {
solutions[num_found] = current
result = result + current
num_solutions = num_solutions + 1
}
}
free(solutions)
free(HEAP)
free(sides)
free(multiples)
return result
}
function main() -> i32 {
printf("%lld\n", solve())
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; }
void heap_push_i64(int64_t v);
int64_t heap_pop(void);
int64_t isqrt_i64(int64_t n);
int64_t bisect_right_ptr_i64_i64_i64(int64_t* sides, int64_t n, int64_t x);
int64_t solve(void);
int32_t main(void);
static const int64_t IGNORE = 2300000000000000;
static const int64_t MAX_COMB = 100;
/* Module statics */
static int64_t* HEAP = NULL;
static int64_t HLEN = 0;
static int64_t HCAP = 0;
void heap_push_i64(int64_t v) {
if ((HLEN + 1) >= HCAP) {
if (HCAP == 0) {
HCAP = 1024;
} else {
HCAP = (HCAP * 2);
}
HEAP = realloc(HEAP, (HCAP * 8));
}
int64_t i = HLEN;
HLEN = (HLEN + 1);
HEAP[i] = v;
while (i > 0) {
int64_t p = FLOW_CHECKED_DIV(((i - 1)), (2));
if (HEAP[p] <= HEAP[i]) {
break;
}
int64_t t = HEAP[p];
HEAP[p] = HEAP[i];
HEAP[i] = t;
i = p;
}
}
int64_t heap_pop(void) {
int64_t res = HEAP[0];
HLEN = (HLEN - 1);
HEAP[0] = HEAP[HLEN];
int64_t i = 0;
while (1) {
int64_t l = ((2 * i) + 1);
int64_t r = (l + 1);
int64_t smallest = i;
if ((l < HLEN && HEAP[l] < HEAP[smallest])) {
smallest = l;
}
if ((r < HLEN && HEAP[r] < HEAP[smallest])) {
smallest = r;
}
if (smallest == i) {
break;
}
int64_t t = HEAP[i];
HEAP[i] = HEAP[smallest];
HEAP[smallest] = t;
i = smallest;
}
return res;
}
int64_t isqrt_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t bisect_right_ptr_i64_i64_i64(int64_t* sides, int64_t n, int64_t x) {
int64_t lo = 0;
int64_t hi = n;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (sides[mid] <= x) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
int64_t solve(void) {
int64_t* solutions = (int64_t*)(calloc((MAX_COMB + 1), 8));
if (solutions == NULL) {
return (-1);
}
int64_t num_solutions = 1;
int64_t result = 0;
HCAP = 4096;
HEAP = calloc(HCAP, 8);
HLEN = 0;
heap_push_i64(1);
int64_t sides_cap = 200000;
int64_t* sides = (int64_t*)(calloc(sides_cap, 8));
int64_t sides_len = 0;
if (sides == NULL) {
return (-1);
}
int64_t* multiples = (int64_t*)(calloc(9, 8));
multiples[0] = 23;
multiples[1] = 19;
multiples[2] = 17;
multiples[3] = 13;
multiples[4] = 11;
multiples[5] = 7;
multiples[6] = 5;
multiples[7] = 3;
multiples[8] = 2;
while (num_solutions < MAX_COMB) {
int64_t current = heap_pop();
if ((current * current) <= IGNORE) {
if ((sides_len + 1) >= sides_cap) {
sides_cap = (sides_cap * 2);
sides = realloc(sides, (sides_cap * 8));
}
sides[sides_len] = current;
sides_len = (sides_len + 1);
}
int64_t mi = 0;
while (mi < 9) {
int64_t multiple = multiples[mi];
int64_t next_value = (multiple * current);
if (next_value <= IGNORE) {
heap_push_i64(next_value);
}
if (FLOW_CHECKED_MOD((current), (multiple)) == 0) {
break;
}
mi = (mi + 1);
}
if (num_solutions >= 56) {
if (FLOW_CHECKED_MOD((current), (800)) != 0) {
continue;
}
} else if (num_solutions >= 8) {
if (FLOW_CHECKED_MOD((current), (80)) != 0) {
continue;
}
} else if (FLOW_CHECKED_MOD((current), (40)) != 0) {
continue;
}
int64_t idx = (bisect_right_ptr_i64_i64_i64(sides, sides_len, isqrt_i64(current)) - 1);
if (idx <= 0) {
continue;
}
int64_t num_found = 0;
while (idx > 0) {
int64_t short_side = sides[idx];
idx = (idx - 1);
int64_t long_side = FLOW_CHECKED_DIV((current), (short_side));
if ((long_side * 10) > (short_side * 11)) {
break;
}
if ((long_side * short_side) == current) {
num_found = (num_found + 1);
}
}
if ((num_found < 2 || num_found > MAX_COMB)) {
continue;
}
if (solutions[num_found] == 0) {
solutions[num_found] = current;
result = (result + current);
num_solutions = (num_solutions + 1);
}
}
free(solutions);
free(HEAP);
free(sides);
free(multiples);
return result;
}
int32_t main(void) {
printf("%lld\n", solve());
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 private @realloc(!llvm.ptr, i64) -> !llvm.ptr
// Constant: IGNORE
llvm.mlir.global internal constant @IGNORE(2300000000000000 : i64) : i64
// Constant: MAX_COMB
llvm.mlir.global internal constant @MAX_COMB(100 : i64) : i64
// Module static: HEAP
llvm.mlir.global internal @HEAP() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: HLEN
llvm.mlir.global internal @HLEN(0 : i64) : i64
// Module static: HCAP
llvm.mlir.global internal @HCAP(0 : i64) : i64
func.func @heap_push(%arg0: i64) -> () {
%1 = llvm.mlir.addressof @HLEN : !llvm.ptr
%2 = llvm.load %1 : !llvm.ptr -> i64
%3 = arith.constant 1 : i32
%5 = arith.extsi %3 : i32 to i64
%4 = arith.addi %2, %5 : i64
%6 = llvm.mlir.addressof @HCAP : !llvm.ptr
%7 = llvm.load %6 : !llvm.ptr -> i64
%8 = arith.cmpi sge, %4, %7 : i64
cf.cond_br %8, ^bb0, ^bb1
^bb0:
%9 = llvm.mlir.addressof @HCAP : !llvm.ptr
%10 = llvm.load %9 : !llvm.ptr -> i64
%11 = arith.constant 0 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.cmpi eq, %10, %13 : i64
cf.cond_br %12, ^bb3, ^bb4
^bb3:
%14 = arith.constant 1024 : i32
%15 = arith.extsi %14 : i32 to i64
%16 = llvm.mlir.addressof @HCAP : !llvm.ptr
llvm.store %15, %16 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
%17 = llvm.mlir.addressof @HCAP : !llvm.ptr
%18 = llvm.load %17 : !llvm.ptr -> i64
%19 = arith.constant 2 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.muli %18, %21 : i64
%22 = llvm.mlir.addressof @HCAP : !llvm.ptr
llvm.store %20, %22 : i64, !llvm.ptr
cf.br ^bb5
^bb5:
%24 = llvm.mlir.addressof @HEAP : !llvm.ptr
%25 = llvm.load %24 : !llvm.ptr -> !llvm.ptr
%26 = llvm.mlir.addressof @HCAP : !llvm.ptr
%27 = llvm.load %26 : !llvm.ptr -> i64
%28 = arith.constant 8 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.muli %27, %30 : i64
%23 = func.call @realloc(%25, %29) : (!llvm.ptr, i64) -> !llvm.ptr
%31 = llvm.mlir.addressof @HEAP : !llvm.ptr
llvm.store %23, %31 : !llvm.ptr, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%32 = llvm.mlir.addressof @HLEN : !llvm.ptr
%33 = llvm.load %32 : !llvm.ptr -> i64
%34 = llvm.mlir.constant(1 : i64) : i64
%35 = llvm.alloca %34 x i64 : (i64) -> !llvm.ptr
llvm.store %33, %35 : i64, !llvm.ptr
%36 = llvm.mlir.addressof @HLEN : !llvm.ptr
%37 = llvm.load %36 : !llvm.ptr -> i64
%38 = arith.constant 1 : i32
%40 = arith.extsi %38 : i32 to i64
%39 = arith.addi %37, %40 : i64
%41 = llvm.mlir.addressof @HLEN : !llvm.ptr
llvm.store %39, %41 : i64, !llvm.ptr
%42 = llvm.mlir.addressof @HEAP : !llvm.ptr
%43 = llvm.load %42 : !llvm.ptr -> !llvm.ptr
%44 = llvm.load %35 : !llvm.ptr -> i64
%45 = llvm.getelementptr %43[%44] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg0, %45 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%46 = llvm.load %35 : !llvm.ptr -> i64
%47 = arith.constant 0 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.cmpi sgt, %46, %49 : i64
cf.cond_br %48, ^bb7, ^bb8
^bb7:
%50 = llvm.load %35 : !llvm.ptr -> i64
%51 = arith.constant 1 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.subi %50, %53 : i64
%54 = arith.constant 2 : i32
%56 = arith.extsi %54 : i32 to i64
%55 = arith.divsi %52, %56 : i64
%58 = llvm.mlir.addressof @HEAP : !llvm.ptr
%59 = llvm.load %58 : !llvm.ptr -> !llvm.ptr
%60 = llvm.getelementptr %59[%55] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%57 = llvm.load %60 : !llvm.ptr -> i64
%62 = llvm.mlir.addressof @HEAP : !llvm.ptr
%63 = llvm.load %62 : !llvm.ptr -> !llvm.ptr
%64 = llvm.load %35 : !llvm.ptr -> i64
%65 = llvm.getelementptr %63[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%61 = llvm.load %65 : !llvm.ptr -> i64
%66 = arith.cmpi sle, %57, %61 : i64
cf.cond_br %66, ^bb9, ^bb10
^bb9:
cf.br ^bb8
^bb10:
cf.br ^bb11
^bb11:
%68 = llvm.mlir.addressof @HEAP : !llvm.ptr
%69 = llvm.load %68 : !llvm.ptr -> !llvm.ptr
%70 = llvm.getelementptr %69[%55] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%67 = llvm.load %70 : !llvm.ptr -> i64
%72 = llvm.mlir.addressof @HEAP : !llvm.ptr
%73 = llvm.load %72 : !llvm.ptr -> !llvm.ptr
%74 = llvm.load %35 : !llvm.ptr -> i64
%75 = llvm.getelementptr %73[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%71 = llvm.load %75 : !llvm.ptr -> i64
%76 = llvm.mlir.addressof @HEAP : !llvm.ptr
%77 = llvm.load %76 : !llvm.ptr -> !llvm.ptr
%78 = llvm.getelementptr %77[%55] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %71, %78 : i64, !llvm.ptr
%79 = llvm.mlir.addressof @HEAP : !llvm.ptr
%80 = llvm.load %79 : !llvm.ptr -> !llvm.ptr
%81 = llvm.load %35 : !llvm.ptr -> i64
%82 = llvm.getelementptr %80[%81] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %67, %82 : i64, !llvm.ptr
llvm.store %55, %35 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
func.return
}
func.func @heap_pop() -> i64 {
%84 = llvm.mlir.addressof @HEAP : !llvm.ptr
%85 = llvm.load %84 : !llvm.ptr -> !llvm.ptr
%86 = arith.constant 0 : i32
%87 = arith.extsi %86 : i32 to i64
%88 = llvm.getelementptr %85[%87] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%83 = llvm.load %88 : !llvm.ptr -> i64
%89 = llvm.mlir.addressof @HLEN : !llvm.ptr
%90 = llvm.load %89 : !llvm.ptr -> i64
%91 = arith.constant 1 : i32
%93 = arith.extsi %91 : i32 to i64
%92 = arith.subi %90, %93 : i64
%94 = llvm.mlir.addressof @HLEN : !llvm.ptr
llvm.store %92, %94 : i64, !llvm.ptr
%96 = llvm.mlir.addressof @HEAP : !llvm.ptr
%97 = llvm.load %96 : !llvm.ptr -> !llvm.ptr
%98 = llvm.mlir.addressof @HLEN : !llvm.ptr
%99 = llvm.load %98 : !llvm.ptr -> i64
%100 = llvm.getelementptr %97[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%95 = llvm.load %100 : !llvm.ptr -> i64
%101 = llvm.mlir.addressof @HEAP : !llvm.ptr
%102 = llvm.load %101 : !llvm.ptr -> !llvm.ptr
%103 = arith.constant 0 : i32
%104 = arith.extsi %103 : i32 to i64
%105 = llvm.getelementptr %102[%104] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %95, %105 : i64, !llvm.ptr
%106 = arith.constant 0 : i32
%107 = arith.extsi %106 : i32 to i64
%108 = llvm.mlir.constant(1 : i64) : i64
%109 = llvm.alloca %108 x i64 : (i64) -> !llvm.ptr
llvm.store %107, %109 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%110 = arith.constant 1 : i1
cf.cond_br %110, ^bb13, ^bb14
^bb13:
%111 = arith.constant 2 : i32
%112 = llvm.load %109 : !llvm.ptr -> i64
%114 = arith.extsi %111 : i32 to i64
%113 = arith.muli %114, %112 : i64
%115 = arith.constant 1 : i32
%117 = arith.extsi %115 : i32 to i64
%116 = arith.addi %113, %117 : i64
%118 = arith.constant 1 : i32
%120 = arith.extsi %118 : i32 to i64
%119 = arith.addi %116, %120 : i64
%121 = llvm.load %109 : !llvm.ptr -> i64
%122 = llvm.mlir.constant(1 : i64) : i64
%123 = llvm.alloca %122 x i64 : (i64) -> !llvm.ptr
llvm.store %121, %123 : i64, !llvm.ptr
%124 = llvm.mlir.addressof @HLEN : !llvm.ptr
%125 = llvm.load %124 : !llvm.ptr -> i64
%126 = arith.cmpi slt, %116, %125 : i64
%127 = scf.if %126 -> (i1) {
%129 = llvm.mlir.addressof @HEAP : !llvm.ptr
%130 = llvm.load %129 : !llvm.ptr -> !llvm.ptr
%131 = llvm.getelementptr %130[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%128 = llvm.load %131 : !llvm.ptr -> i64
%133 = llvm.mlir.addressof @HEAP : !llvm.ptr
%134 = llvm.load %133 : !llvm.ptr -> !llvm.ptr
%135 = llvm.load %123 : !llvm.ptr -> i64
%136 = llvm.getelementptr %134[%135] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%132 = llvm.load %136 : !llvm.ptr -> i64
%137 = arith.cmpi slt, %128, %132 : i64
scf.yield %137 : i1
} else {
%138 = arith.constant false
scf.yield %138 : i1
}
cf.cond_br %127, ^bb15, ^bb16
^bb15:
llvm.store %116, %123 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%139 = llvm.mlir.addressof @HLEN : !llvm.ptr
%140 = llvm.load %139 : !llvm.ptr -> i64
%141 = arith.cmpi slt, %119, %140 : i64
%142 = scf.if %141 -> (i1) {
%144 = llvm.mlir.addressof @HEAP : !llvm.ptr
%145 = llvm.load %144 : !llvm.ptr -> !llvm.ptr
%146 = llvm.getelementptr %145[%119] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%143 = llvm.load %146 : !llvm.ptr -> i64
%148 = llvm.mlir.addressof @HEAP : !llvm.ptr
%149 = llvm.load %148 : !llvm.ptr -> !llvm.ptr
%150 = llvm.load %123 : !llvm.ptr -> i64
%151 = llvm.getelementptr %149[%150] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%147 = llvm.load %151 : !llvm.ptr -> i64
%152 = arith.cmpi slt, %143, %147 : i64
scf.yield %152 : i1
} else {
%153 = arith.constant false
scf.yield %153 : i1
}
cf.cond_br %142, ^bb18, ^bb19
^bb18:
llvm.store %119, %123 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%154 = llvm.load %123 : !llvm.ptr -> i64
%155 = llvm.load %109 : !llvm.ptr -> i64
%156 = arith.cmpi eq, %154, %155 : i64
cf.cond_br %156, ^bb21, ^bb22
^bb21:
cf.br ^bb14
^bb22:
cf.br ^bb23
^bb23:
%158 = llvm.mlir.addressof @HEAP : !llvm.ptr
%159 = llvm.load %158 : !llvm.ptr -> !llvm.ptr
%160 = llvm.load %109 : !llvm.ptr -> i64
%161 = llvm.getelementptr %159[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%157 = llvm.load %161 : !llvm.ptr -> i64
%163 = llvm.mlir.addressof @HEAP : !llvm.ptr
%164 = llvm.load %163 : !llvm.ptr -> !llvm.ptr
%165 = llvm.load %123 : !llvm.ptr -> i64
%166 = llvm.getelementptr %164[%165] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%162 = llvm.load %166 : !llvm.ptr -> i64
%167 = llvm.mlir.addressof @HEAP : !llvm.ptr
%168 = llvm.load %167 : !llvm.ptr -> !llvm.ptr
%169 = llvm.load %109 : !llvm.ptr -> i64
%170 = llvm.getelementptr %168[%169] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %162, %170 : i64, !llvm.ptr
%171 = llvm.mlir.addressof @HEAP : !llvm.ptr
%172 = llvm.load %171 : !llvm.ptr -> !llvm.ptr
%173 = llvm.load %123 : !llvm.ptr -> i64
%174 = llvm.getelementptr %172[%173] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %157, %174 : i64, !llvm.ptr
%175 = llvm.load %123 : !llvm.ptr -> i64
llvm.store %175, %109 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
func.return %83 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%176 = arith.constant 0 : i32
%178 = arith.extsi %176 : i32 to i64
%177 = arith.cmpi sle, %arg0, %178 : i64
cf.cond_br %177, ^bb24, ^bb25
^bb24:
%179 = arith.constant 0 : i32
%180 = arith.extsi %179 : i32 to i64
func.return %180 : i64
^bb25:
cf.br ^bb26
^bb26:
%181 = llvm.mlir.constant(1 : i64) : i64
%182 = llvm.alloca %181 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %182 : i64, !llvm.ptr
%183 = llvm.load %182 : !llvm.ptr -> i64
%184 = arith.constant 1 : i32
%186 = arith.extsi %184 : i32 to i64
%185 = arith.addi %183, %186 : i64
%187 = arith.constant 2 : i32
%189 = arith.extsi %187 : i32 to i64
%188 = arith.divsi %185, %189 : i64
%190 = llvm.mlir.constant(1 : i64) : i64
%191 = llvm.alloca %190 x i64 : (i64) -> !llvm.ptr
llvm.store %188, %191 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%192 = llvm.load %191 : !llvm.ptr -> i64
%193 = llvm.load %182 : !llvm.ptr -> i64
%194 = arith.cmpi slt, %192, %193 : i64
cf.cond_br %194, ^bb28, ^bb29
^bb28:
%195 = llvm.load %191 : !llvm.ptr -> i64
llvm.store %195, %182 : i64, !llvm.ptr
%196 = llvm.load %182 : !llvm.ptr -> i64
%197 = llvm.load %182 : !llvm.ptr -> i64
%198 = arith.divsi %arg0, %197 : i64
%199 = arith.addi %196, %198 : i64
%200 = arith.constant 2 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.divsi %199, %202 : i64
llvm.store %201, %191 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%203 = llvm.load %182 : !llvm.ptr -> i64
func.return %203 : i64
}
func.func @bisect_right(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%204 = arith.constant 0 : i32
%205 = arith.extsi %204 : i32 to i64
%206 = llvm.mlir.constant(1 : i64) : i64
%207 = llvm.alloca %206 x i64 : (i64) -> !llvm.ptr
llvm.store %205, %207 : i64, !llvm.ptr
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %209 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%210 = llvm.load %207 : !llvm.ptr -> i64
%211 = llvm.load %209 : !llvm.ptr -> i64
%212 = arith.cmpi slt, %210, %211 : i64
cf.cond_br %212, ^bb31, ^bb32
^bb31:
%213 = llvm.load %207 : !llvm.ptr -> i64
%214 = llvm.load %209 : !llvm.ptr -> i64
%215 = arith.addi %213, %214 : i64
%216 = arith.constant 2 : i32
%218 = arith.extsi %216 : i32 to i64
%217 = arith.divsi %215, %218 : i64
%220 = llvm.getelementptr %arg0[%217] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%219 = llvm.load %220 : !llvm.ptr -> i64
%221 = arith.cmpi sle, %219, %arg2 : i64
cf.cond_br %221, ^bb33, ^bb34
^bb33:
%222 = arith.constant 1 : i32
%224 = arith.extsi %222 : i32 to i64
%223 = arith.addi %217, %224 : i64
llvm.store %223, %207 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
llvm.store %217, %209 : i64, !llvm.ptr
cf.br ^bb35
^bb35:
cf.br ^bb30
^bb32:
%225 = llvm.load %207 : !llvm.ptr -> i64
func.return %225 : i64
}
func.func @solve() -> i64 {
%227 = llvm.mlir.addressof @MAX_COMB : !llvm.ptr
%228 = llvm.load %227 : !llvm.ptr -> i64
%229 = arith.constant 1 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.addi %228, %231 : i64
%232 = arith.constant 8 : i32
%233 = arith.extsi %232 : i32 to i64
%226 = func.call @calloc(%230, %233) : (i64, i64) -> !llvm.ptr
%234 = llvm.mlir.zero : !llvm.ptr
%235 = llvm.icmp "eq" %226, %234 : !llvm.ptr
cf.cond_br %235, ^bb36, ^bb37
^bb36:
%236 = arith.constant 1 : i32
%238 = arith.constant 0 : i32
%237 = arith.subi %238, %236 : i32
%239 = arith.extsi %237 : i32 to i64
func.return %239 : i64
^bb37:
cf.br ^bb38
^bb38:
%240 = arith.constant 1 : i32
%241 = arith.extsi %240 : i32 to i64
%242 = llvm.mlir.constant(1 : i64) : i64
%243 = llvm.alloca %242 x i64 : (i64) -> !llvm.ptr
llvm.store %241, %243 : i64, !llvm.ptr
%244 = arith.constant 0 : i32
%245 = arith.extsi %244 : i32 to i64
%246 = llvm.mlir.constant(1 : i64) : i64
%247 = llvm.alloca %246 x i64 : (i64) -> !llvm.ptr
llvm.store %245, %247 : i64, !llvm.ptr
%248 = arith.constant 4096 : i32
%249 = arith.extsi %248 : i32 to i64
%250 = llvm.mlir.addressof @HCAP : !llvm.ptr
llvm.store %249, %250 : i64, !llvm.ptr
%252 = llvm.mlir.addressof @HCAP : !llvm.ptr
%253 = llvm.load %252 : !llvm.ptr -> i64
%254 = arith.constant 8 : i32
%255 = arith.extsi %254 : i32 to i64
%251 = func.call @calloc(%253, %255) : (i64, i64) -> !llvm.ptr
%256 = llvm.mlir.addressof @HEAP : !llvm.ptr
llvm.store %251, %256 : !llvm.ptr, !llvm.ptr
%257 = arith.constant 0 : i32
%258 = arith.extsi %257 : i32 to i64
%259 = llvm.mlir.addressof @HLEN : !llvm.ptr
llvm.store %258, %259 : i64, !llvm.ptr
%261 = arith.constant 1 : i32
%262 = arith.extsi %261 : i32 to i64
func.call @heap_push(%262) : (i64) -> ()
%263 = arith.constant 200000 : i32
%264 = arith.extsi %263 : i32 to i64
%265 = llvm.mlir.constant(1 : i64) : i64
%266 = llvm.alloca %265 x i64 : (i64) -> !llvm.ptr
llvm.store %264, %266 : i64, !llvm.ptr
%268 = llvm.load %266 : !llvm.ptr -> i64
%269 = arith.constant 8 : i32
%270 = arith.extsi %269 : i32 to i64
%267 = func.call @calloc(%268, %270) : (i64, i64) -> !llvm.ptr
%271 = llvm.mlir.constant(1 : i64) : i64
%272 = llvm.alloca %271 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %267, %272 : !llvm.ptr, !llvm.ptr
%273 = arith.constant 0 : i32
%274 = arith.extsi %273 : i32 to i64
%275 = llvm.mlir.constant(1 : i64) : i64
%276 = llvm.alloca %275 x i64 : (i64) -> !llvm.ptr
llvm.store %274, %276 : i64, !llvm.ptr
%277 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
%278 = llvm.mlir.zero : !llvm.ptr
%279 = llvm.icmp "eq" %277, %278 : !llvm.ptr
cf.cond_br %279, ^bb39, ^bb40
^bb39:
%280 = arith.constant 1 : i32
%282 = arith.constant 0 : i32
%281 = arith.subi %282, %280 : i32
%283 = arith.extsi %281 : i32 to i64
func.return %283 : i64
^bb40:
cf.br ^bb41
^bb41:
%285 = arith.constant 9 : i32
%286 = arith.constant 8 : i32
%287 = arith.extsi %285 : i32 to i64
%288 = arith.extsi %286 : i32 to i64
%284 = func.call @calloc(%287, %288) : (i64, i64) -> !llvm.ptr
%289 = arith.constant 23 : i32
%290 = arith.constant 0 : i32
%291 = arith.extsi %289 : i32 to i64
%292 = arith.extsi %290 : i32 to i64
%293 = llvm.getelementptr %284[%292] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %291, %293 : i64, !llvm.ptr
%294 = arith.constant 19 : i32
%295 = arith.constant 1 : i32
%296 = arith.extsi %294 : i32 to i64
%297 = arith.extsi %295 : i32 to i64
%298 = llvm.getelementptr %284[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %296, %298 : i64, !llvm.ptr
%299 = arith.constant 17 : i32
%300 = arith.constant 2 : i32
%301 = arith.extsi %299 : i32 to i64
%302 = arith.extsi %300 : i32 to i64
%303 = llvm.getelementptr %284[%302] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %301, %303 : i64, !llvm.ptr
%304 = arith.constant 13 : i32
%305 = arith.constant 3 : i32
%306 = arith.extsi %304 : i32 to i64
%307 = arith.extsi %305 : i32 to i64
%308 = llvm.getelementptr %284[%307] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %306, %308 : i64, !llvm.ptr
%309 = arith.constant 11 : i32
%310 = arith.constant 4 : i32
%311 = arith.extsi %309 : i32 to i64
%312 = arith.extsi %310 : i32 to i64
%313 = llvm.getelementptr %284[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %311, %313 : i64, !llvm.ptr
%314 = arith.constant 7 : i32
%315 = arith.constant 5 : i32
%316 = arith.extsi %314 : i32 to i64
%317 = arith.extsi %315 : i32 to i64
%318 = llvm.getelementptr %284[%317] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %316, %318 : i64, !llvm.ptr
%319 = arith.constant 5 : i32
%320 = arith.constant 6 : i32
%321 = arith.extsi %319 : i32 to i64
%322 = arith.extsi %320 : i32 to i64
%323 = llvm.getelementptr %284[%322] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %321, %323 : i64, !llvm.ptr
%324 = arith.constant 3 : i32
%325 = arith.constant 7 : i32
%326 = arith.extsi %324 : i32 to i64
%327 = arith.extsi %325 : i32 to i64
%328 = llvm.getelementptr %284[%327] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %326, %328 : i64, !llvm.ptr
%329 = arith.constant 2 : i32
%330 = arith.constant 8 : i32
%331 = arith.extsi %329 : i32 to i64
%332 = arith.extsi %330 : i32 to i64
%333 = llvm.getelementptr %284[%332] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %331, %333 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%334 = llvm.load %243 : !llvm.ptr -> i64
%335 = llvm.mlir.addressof @MAX_COMB : !llvm.ptr
%336 = llvm.load %335 : !llvm.ptr -> i64
%337 = arith.cmpi slt, %334, %336 : i64
cf.cond_br %337, ^bb43, ^bb44
^bb43:
%338 = func.call @heap_pop() : () -> i64
%339 = arith.muli %338, %338 : i64
%340 = llvm.mlir.addressof @IGNORE : !llvm.ptr
%341 = llvm.load %340 : !llvm.ptr -> i64
%342 = arith.cmpi sle, %339, %341 : i64
cf.cond_br %342, ^bb45, ^bb46
^bb45:
%343 = llvm.load %276 : !llvm.ptr -> i64
%344 = arith.constant 1 : i32
%346 = arith.extsi %344 : i32 to i64
%345 = arith.addi %343, %346 : i64
%347 = llvm.load %266 : !llvm.ptr -> i64
%348 = arith.cmpi sge, %345, %347 : i64
cf.cond_br %348, ^bb48, ^bb49
^bb48:
%349 = llvm.load %266 : !llvm.ptr -> i64
%350 = arith.constant 2 : i32
%352 = arith.extsi %350 : i32 to i64
%351 = arith.muli %349, %352 : i64
llvm.store %351, %266 : i64, !llvm.ptr
%354 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
%355 = llvm.load %266 : !llvm.ptr -> i64
%356 = arith.constant 8 : i32
%358 = arith.extsi %356 : i32 to i64
%357 = arith.muli %355, %358 : i64
%353 = func.call @realloc(%354, %357) : (!llvm.ptr, i64) -> !llvm.ptr
llvm.store %353, %272 : !llvm.ptr, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%359 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
%360 = llvm.load %276 : !llvm.ptr -> i64
%361 = llvm.getelementptr %359[%360] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %338, %361 : i64, !llvm.ptr
%362 = llvm.load %276 : !llvm.ptr -> i64
%363 = arith.constant 1 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.addi %362, %365 : i64
llvm.store %364, %276 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%366 = arith.constant 0 : i32
%367 = arith.extsi %366 : i32 to i64
%368 = llvm.mlir.constant(1 : i64) : i64
%369 = llvm.alloca %368 x i64 : (i64) -> !llvm.ptr
llvm.store %367, %369 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%370 = llvm.load %369 : !llvm.ptr -> i64
%371 = arith.constant 9 : i32
%373 = arith.extsi %371 : i32 to i64
%372 = arith.cmpi slt, %370, %373 : i64
cf.cond_br %372, ^bb52, ^bb53
^bb52:
%375 = llvm.load %369 : !llvm.ptr -> i64
%376 = llvm.getelementptr %284[%375] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%374 = llvm.load %376 : !llvm.ptr -> i64
%377 = arith.muli %374, %338 : i64
%378 = llvm.mlir.addressof @IGNORE : !llvm.ptr
%379 = llvm.load %378 : !llvm.ptr -> i64
%380 = arith.cmpi sle, %377, %379 : i64
cf.cond_br %380, ^bb54, ^bb55
^bb54:
func.call @heap_push(%377) : (i64) -> ()
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%382 = arith.remsi %338, %374 : i64
%383 = arith.constant 0 : i32
%385 = arith.extsi %383 : i32 to i64
%384 = arith.cmpi eq, %382, %385 : i64
cf.cond_br %384, ^bb57, ^bb58
^bb57:
cf.br ^bb53
^bb58:
cf.br ^bb59
^bb59:
%386 = llvm.load %369 : !llvm.ptr -> i64
%387 = arith.constant 1 : i32
%389 = arith.extsi %387 : i32 to i64
%388 = arith.addi %386, %389 : i64
llvm.store %388, %369 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%390 = llvm.load %243 : !llvm.ptr -> i64
%391 = arith.constant 56 : i32
%393 = arith.extsi %391 : i32 to i64
%392 = arith.cmpi sge, %390, %393 : i64
cf.cond_br %392, ^bb60, ^bb61
^bb60:
%394 = arith.constant 800 : i32
%396 = arith.extsi %394 : i32 to i64
%395 = arith.remsi %338, %396 : i64
%397 = arith.constant 0 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.cmpi ne, %395, %399 : i64
cf.cond_br %398, ^bb63, ^bb64
^bb63:
cf.br ^bb42
^bb64:
cf.br ^bb65
^bb65:
cf.br ^bb62
^bb61:
%400 = llvm.load %243 : !llvm.ptr -> i64
%401 = arith.constant 8 : i32
%403 = arith.extsi %401 : i32 to i64
%402 = arith.cmpi sge, %400, %403 : i64
cf.cond_br %402, ^bb67, ^bb66
^bb67:
%404 = arith.constant 80 : i32
%406 = arith.extsi %404 : i32 to i64
%405 = arith.remsi %338, %406 : i64
%407 = arith.constant 0 : i32
%409 = arith.extsi %407 : i32 to i64
%408 = arith.cmpi ne, %405, %409 : i64
cf.cond_br %408, ^bb68, ^bb69
^bb68:
cf.br ^bb42
^bb69:
cf.br ^bb70
^bb70:
cf.br ^bb62
^bb66:
%410 = arith.constant 40 : i32
%412 = arith.extsi %410 : i32 to i64
%411 = arith.remsi %338, %412 : i64
%413 = arith.constant 0 : i32
%415 = arith.extsi %413 : i32 to i64
%414 = arith.cmpi ne, %411, %415 : i64
cf.cond_br %414, ^bb71, ^bb62
^bb71:
cf.br ^bb42
^bb62:
%417 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
%418 = llvm.load %276 : !llvm.ptr -> i64
%419 = func.call @isqrt(%338) : (i64) -> i64
%416 = func.call @bisect_right(%417, %418, %419) : (!llvm.ptr, i64, i64) -> i64
%420 = arith.constant 1 : i32
%422 = arith.extsi %420 : i32 to i64
%421 = arith.subi %416, %422 : i64
%423 = llvm.mlir.constant(1 : i64) : i64
%424 = llvm.alloca %423 x i64 : (i64) -> !llvm.ptr
llvm.store %421, %424 : i64, !llvm.ptr
%425 = llvm.load %424 : !llvm.ptr -> i64
%426 = arith.constant 0 : i32
%428 = arith.extsi %426 : i32 to i64
%427 = arith.cmpi sle, %425, %428 : i64
cf.cond_br %427, ^bb72, ^bb73
^bb72:
cf.br ^bb42
^bb73:
cf.br ^bb74
^bb74:
%429 = arith.constant 0 : i32
%430 = arith.extsi %429 : i32 to i64
%431 = llvm.mlir.constant(1 : i64) : i64
%432 = llvm.alloca %431 x i64 : (i64) -> !llvm.ptr
llvm.store %430, %432 : i64, !llvm.ptr
cf.br ^bb75
^bb75:
%433 = llvm.load %424 : !llvm.ptr -> i64
%434 = arith.constant 0 : i32
%436 = arith.extsi %434 : i32 to i64
%435 = arith.cmpi sgt, %433, %436 : i64
cf.cond_br %435, ^bb76, ^bb77
^bb76:
%438 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
%439 = llvm.load %424 : !llvm.ptr -> i64
%440 = llvm.getelementptr %438[%439] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%437 = llvm.load %440 : !llvm.ptr -> i64
%441 = llvm.load %424 : !llvm.ptr -> i64
%442 = arith.constant 1 : i32
%444 = arith.extsi %442 : i32 to i64
%443 = arith.subi %441, %444 : i64
llvm.store %443, %424 : i64, !llvm.ptr
%445 = arith.divsi %338, %437 : i64
%446 = arith.constant 10 : i32
%448 = arith.extsi %446 : i32 to i64
%447 = arith.muli %445, %448 : i64
%449 = arith.constant 11 : i32
%451 = arith.extsi %449 : i32 to i64
%450 = arith.muli %437, %451 : i64
%452 = arith.cmpi sgt, %447, %450 : i64
cf.cond_br %452, ^bb78, ^bb79
^bb78:
cf.br ^bb77
^bb79:
cf.br ^bb80
^bb80:
%453 = arith.muli %445, %437 : i64
%454 = arith.cmpi eq, %453, %338 : i64
cf.cond_br %454, ^bb81, ^bb82
^bb81:
%455 = llvm.load %432 : !llvm.ptr -> i64
%456 = arith.constant 1 : i32
%458 = arith.extsi %456 : i32 to i64
%457 = arith.addi %455, %458 : i64
llvm.store %457, %432 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
cf.br ^bb75
^bb77:
%459 = llvm.load %432 : !llvm.ptr -> i64
%460 = arith.constant 2 : i32
%462 = arith.extsi %460 : i32 to i64
%461 = arith.cmpi slt, %459, %462 : i64
%463 = scf.if %461 -> (i1) {
%464 = arith.constant true
scf.yield %464 : i1
} else {
%465 = llvm.load %432 : !llvm.ptr -> i64
%466 = llvm.mlir.addressof @MAX_COMB : !llvm.ptr
%467 = llvm.load %466 : !llvm.ptr -> i64
%468 = arith.cmpi sgt, %465, %467 : i64
scf.yield %468 : i1
}
cf.cond_br %463, ^bb84, ^bb85
^bb84:
cf.br ^bb42
^bb85:
cf.br ^bb86
^bb86:
%470 = llvm.load %432 : !llvm.ptr -> i64
%471 = llvm.getelementptr %226[%470] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%469 = llvm.load %471 : !llvm.ptr -> i64
%472 = arith.constant 0 : i32
%474 = arith.extsi %472 : i32 to i64
%473 = arith.cmpi eq, %469, %474 : i64
cf.cond_br %473, ^bb87, ^bb88
^bb87:
%475 = llvm.load %432 : !llvm.ptr -> i64
%476 = llvm.getelementptr %226[%475] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %338, %476 : i64, !llvm.ptr
%477 = llvm.load %247 : !llvm.ptr -> i64
%478 = arith.addi %477, %338 : i64
llvm.store %478, %247 : i64, !llvm.ptr
%479 = llvm.load %243 : !llvm.ptr -> i64
%480 = arith.constant 1 : i32
%482 = arith.extsi %480 : i32 to i64
%481 = arith.addi %479, %482 : i64
llvm.store %481, %243 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
cf.br ^bb42
^bb44:
func.call @free(%226) : (!llvm.ptr) -> ()
%485 = llvm.mlir.addressof @HEAP : !llvm.ptr
%486 = llvm.load %485 : !llvm.ptr -> !llvm.ptr
func.call @free(%486) : (!llvm.ptr) -> ()
%488 = llvm.load %272 : !llvm.ptr -> !llvm.ptr
func.call @free(%488) : (!llvm.ptr) -> ()
func.call @free(%284) : (!llvm.ptr) -> ()
%490 = llvm.load %247 : !llvm.ptr -> i64
func.return %490 : i64
}
func.func @main() -> i32 {
%491 = llvm.mlir.addressof @str_0 : !llvm.ptr
%492 = func.call @solve() : () -> i64
%493 = llvm.call @printf(%491, %492) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%494 = arith.constant 0 : i32
func.return %494 : i32
}
}