#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef unsigned char byte;

byte *pool, *pool_ptr, *helper, *helper_ptr;
size_t pool_size, left_space;
const byte SIZE_MARK_MAX = UCHAR_MAX >> 1;

void use_mj_allocator(size_t size)
{
    pool = pool_ptr = (byte *)malloc(size);
    helper = helper_ptr = (byte *)calloc(size, 1);
    pool_size = left_space = size;
}

void free_mj_allocator()
{
    free(pool);
    free(helper);
}

void set_size_mark(size_t size, byte *ptr)
{
    if (size <= SIZE_MARK_MAX)
    {
        *ptr = (size << 1) + 1;
    }
    else
    {
        *ptr = 2;
        *(size_t *)(ptr + 1) = size;
    }
}

size_t get_size_mark(const byte *ptr)
{
    if (*ptr & 1)
    {
        return *ptr >> 1;
    }
    return *(size_t *)(ptr + 1);
}

int search(size_t size)
{
    if (size > pool_size)
    {
        return 0;
    }
    byte *start_ptr = helper_ptr;
    if (left_space == 0)
    {
        goto no_left_space;
    }
    helper_ptr += left_space;
    left_space = 0;
    while (1)
    {
        if (helper_ptr == start_ptr)
        {
            return 0;
        }
    no_left_space:
        if (helper_ptr == helper + pool_size)
        {
            helper_ptr = helper;
            left_space = 0;
        }
        if (*helper_ptr)
        {
            left_space = 0;
            helper_ptr += get_size_mark(helper_ptr);
        }
        else
        {
            ++left_space;
            ++helper_ptr;
        }
        if (left_space == size)
        {
            while (1)
            {
                if (helper_ptr == helper + pool_size || *helper_ptr)
                {
                    break;
                }
                ++left_space;
                ++helper_ptr;
            }
            break;
        }
    }
    helper_ptr -= left_space;
    pool_ptr = helper_ptr - helper + pool;
    return 1;
}

void *mj_malloc(size_t size)
{
    if (size > left_space)
    {
        if (!search(size))
        {
            return NULL;
        }
    }
    set_size_mark(size, helper_ptr);
    byte *ptr = pool_ptr;
    pool_ptr += size;
    helper_ptr += size;
    left_space -= size;
    return ptr;
}

void *mj_calloc(size_t len, size_t unit)
{
    size_t size = len * unit;
    void *ptr = mj_malloc(size);
    memset(ptr, 0, size);
    return ptr;
}

void mj_free(void *ptr)
{
    byte *temp_helper_ptr = (byte *)ptr - pool + helper;
    if (*temp_helper_ptr & 1)
    {
        *temp_helper_ptr = 0;
    }
    else
    {
        memset(temp_helper_ptr, 0, sizeof(size_t) + 1);
    }
}

size_t kb_to_b(size_t kb)
{
    return 1000 * kb;
}

size_t mb_to_b(size_t mb)
{
    return kb_to_b(1000 * mb);
}

size_t gb_to_b(size_t gb)
{
    return mb_to_b(1000 * gb);
}

#ifndef MJ_ALLOCATOR_H
#define MJ_ALLOCATOR_H

#include <stddef.h>

#define malloc mj_malloc
#define calloc mj_calloc
#define free mj_free

void use_mj_allocator(size_t size);
void free_mj_allocator();
void *mj_malloc(size_t size);
void *mj_calloc(size_t len, size_t unit);
void mj_free(void *ptr);
size_t kb_to_b(size_t kb);
size_t mb_to_b(size_t mb);
size_t gb_to_b(size_t gb);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#ifdef MJ_ALLOCATOR
#include "mj_allocator.h"
#endif

enum {ARRAY_LEN = 50000};
int *array[ARRAY_LEN];
long long sum = 0;

int confuse_the_compiler(int n)
{
    return n % 10 > 5 ? -n / 2 : n * 2;
}

void start()
{
    for (int i = 1; i <= ARRAY_LEN; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            array[j] = (int *)malloc(sizeof(int));
            array[j][0] = j + 1;
        }
        for (int j = i - 1; j >= 0; --j)
        {
            sum -= j;
            int n = confuse_the_compiler(array[j][0]);
            if (n != 0)
            {
                sum += n;
                free(array[j]);
            }
        }
    }
}

int main()
{

#ifdef MJ_ALLOCATOR
    use_mj_allocator(ARRAY_LEN * sizeof(int));
#endif

    time_t start_time = clock();
    start();
    time_t end_time = clock();
    printf("nelapsed time: %.3fn", (double)(end_time - start_time) / CLOCKS_PER_SEC);
    printf("%lld", sum);

#ifdef MJ_ALLOCATOR
    free_mj_allocator();
#endif

    return 0;
}

class test
{
    final static int ARRAY_LEN = 50000;
    static int[][] array;
    static long sum = 0;

    static int confuse_the_compiler(int n)
    {
        return n % 10 > 5 ? -n / 2 : n * 2;
    }

    static void start()
    {
        for (int i = 1; i <= ARRAY_LEN; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                array[j] = new int[1];
                array[j][0] = j + 1;
            }
            for (int j = i - 1; j >= 0; --j)
            {
                sum -= j;
                int n = confuse_the_compiler(array[j][0]);
                if (n != 0)
                {
                    sum += n;
                    // free(array[j]);
                }
            }
        }
    }

    public static void main(String[] args)
    {
        array = new int[ARRAY_LEN][];
        long start_time = System.currentTimeMillis();
        start();
        System.gc();
        long end_time = System.currentTimeMillis();
        System.out.printf("nelapsed time: %.3fn", (end_time - start_time) / 1000.0);
        System.out.println(sum);
    }
}