#[path = "../lib.rs"]
mod lib;

fn parse_input() -> Vec<u8> {
    let line = lib::iter_input().next().unwrap();
    return line.chars().map(|c| c.to_digit(10).unwrap() as u8).collect();
}

fn part1(orig: &Vec<u8>) -> usize {
    let mut mem = orig.clone();
    let mut sum = 0;
    let mut k = 0;
    let mut acc = 0;
    let mut value;
    let mut count;
    let mut i = 0;
    let mut j = mem.len() - 1;
    if j % 2 == 1 {
        j -= 1;
    }

    while i <= j {
        if i % 2 == 0 {
            value = i / 2;
            count = mem[i];
            i += 1;
        } else {
            value = j / 2;
            count = mem[i].min(mem[j]);

            mem[i] -= count;
            mem[j] -= count;
            if mem[i] == 0 {
                i += 1;
            }
            if mem[j] == 0 {
                j -= 2;
            }
        }

        // println!("add({}, {})", value, count);
        k += count as usize;
        let acc_new = k * (k - 1) / 2;
        sum += value * (acc_new - acc);
        acc = acc_new;
    }

    return sum;
}

fn part2(orig: &Vec<u8>) -> usize {
    let mut mem = orig.clone();
    let mut sum = 0;
    let mut k = 0;
    let mut acc = 0;
    let mut used = vec![false; mem.len()];

    for i in 0..mem.len() {
        if i % 2 == 0 {
            k += mem[i] as usize;
            let acc_new = k * (k - 1) / 2;
            if !used[i] {
                sum += i / 2 * (acc_new - acc);
            }
            acc = acc_new;
        } else {
            for j in (i+1..mem.len()).step_by(2).rev() {
                if !used[j] && mem[j] <= mem[i] {
                    k += mem[j] as usize;
                    let acc_new = k * (k - 1) / 2;
                    sum += j / 2 * (acc_new - acc);
                    acc = acc_new;

                    mem[i] -= mem[j];
                    used[j] = true;
                    if mem[i] == 0 {
                        break;
                    }
                }
            }
            if mem[i] != 0 {
                k += mem[i] as usize;
                acc = k * (k - 1) / 2;
            }
        }
    }

    return sum;
}

fn main() {
    let mem = parse_input();

    println!("part1: {}", part1(&mem));
    println!("part2: {}", part2(&mem));
}