提出 #41927472

---

ソースコード 拡げる

use proconio::input;

fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

const N: usize = 100;
const N_1: i32 = 99;
const M: usize = 1000;
const LOG: [f64; 128] = [-5.545177444, -4.446565156, -3.935739532, -3.599267295, -3.347952867, -3.147282172, -2.980228087, -2.837127243, -2.7119641, -2.600738465, -2.500655007, -2.409683229, -2.32630162, -2.249340578, -2.177881614, -2.11119024, -2.048669883, -1.989829383, -1.934259532, -1.881615798, -1.831605378, -1.783977329, -1.738514955, -1.695029843, -1.653357146, -1.613351812, -1.574885531, -1.537844259, -1.502126177, -1.467640001, -1.43430358, -1.402042718, -1.370790175, -1.340484825, -1.31107094, -1.282497567, -1.254718003, -1.227689331, -1.201372023, -1.175729592, -1.15072829, -1.126336837, -1.102526188, -1.079269326, -1.056541075, -1.034317938, -1.012577951, -0.991300553, -0.970466466, -0.950057594, -0.930056928, -0.910448456, -0.891217094, -0.87234861, -0.853829562, -0.835647243, -0.817789626, -0.800245316, -0.78300351, -0.766053951, -0.749386899, -0.732993089, -0.716863707, -0.700990358, -0.68536504, -0.669980121, -0.654828316, -0.639902666, -0.625196519, -0.610703511, -0.596417554, -0.582332814, -0.568443702, -0.554744858, -0.541231139, -0.527897608, -0.514739523, -0.501752328, -0.488931639, -0.476273242, -0.463773079, -0.451427244, -0.439231971, -0.427183632, -0.41527873, -0.403513888, -0.39188585, -0.380391471, -0.369027712, -0.357791639, -0.346680413, -0.335691292, -0.324821619, -0.314068828, -0.303430429, -0.292904016, -0.282487256, -0.272177886, -0.261973716, -0.25187262, -0.241872536, -0.231971465, -0.222167465, -0.212458651, -0.202843193, -0.193319311, -0.183885279, -0.174539416, -0.165280091, -0.156105715, -0.147014743, -0.138005673, -0.129077042, -0.120227427, -0.111455441, -0.102759734, -0.094138991, -0.08559193, -0.077117303, -0.068713893, -0.060380511, -0.052116001, -0.043919234, -0.035789108, -0.027724548, -0.019724505, -0.011787956, -0.003913899];

fn main() {
    get_time();
    input! {
        mut a: [[i32; N]; N],
    }

    let mut b = vec![vec![0; N]; N];
    let mut r = vec![9,62,39,5,55,85,53,28,56,1,99,1,69,14,44,56,4,39,78,7,41,16,58,97,63,7,5,60,15,59,32,31,3,43,20,51,72,25,0,52,23,21,61,57,81,14,93,17,76,90,89,38,92,93,88,14,4,99,26,67,11,39,28,5,68,15,48,50,33,70,87,91,90,46,41,42,32,20,7,27,36,72,18,72,29,99,28,24,37,23,28,90,44,21,57,17,87,69,7,81,58,9,61,4,35,50,0,0,34,87,70,69,10,28,26,53,79,43,63,32,82,87,60,17,80,77,61,86,98,73,86,4,22,19,80,50,2,81,82,2,16,67,54,26,79,62,92,45,61,94,12,61,45,16,8,18,28,96,76,47,49,57,49,42,57,53,41,84,84,39,32,7,43,23,72,4,75,23,17,58,19,53,55,17,72,52,39,39,48,96,16,36,1,44,23,27,59,76,28,87,87,80,73,63,0,22,26,26,70,28,48,45,36,43,36,85,21,27,96,13,63,48,39,48,57,81,23,37,16,20,89,86,89,84,78,58,98,33,28,81,4,70,21,10,29,60,97,94,55,60,5,10,77,88,0,34,80,83,54,76,65,19,36,20,46,24,68,49,86,6,35,49,50,35,80,79,81,86,57,14,11,7,60,88,70,5,39,17,61,2,66,47,0,3,47,83,63,77,80,53,68,86,26,39,97,75,36,3,13,54,42,33,22,6,97,76,5,98,97,34,85,85,38,42,41,35,64,55,58,8,17,29,28,82,22,17,53,18,14,63,41,66,58,37,63,91,96,0,48,95,89,24,6,54,97,90,30,40,62,77,96,92,12,32,34,88,92,67,53,52,58,20,40,74,96,15,28,51,46,69,55,18,94,18,26,87,1,44,13,95,91,53,40,73,17,72,26,89,62,98,79,16,50,4,1,86,29,58,19,87,8,27,15,62,64,64,72,36,59,13,63,50,51,35,14,93,21,65,88,89,5,60,62,60,20,54,61,47,29,71,43,93,9,30,64,0,98,73,52,41,94,66,33,84,41,68,68,10,43,89,16,12,21,75,4,11,26,78,92,51,71,38,34,76,67,58,23,1,8,41,50,97,50,70,44,13,55,20,80,70,88,20,98,93,18,25,38,95,98,78,27,8,73,33,70,45,94,29,43,33,90,17,11,44,49,76,71,89,19,65,94,33,24,52,96,62,95,70,81,53,0,95,60,83,78,2,7,92,66,4,38,90,54,9,22,12,17,31,4,3,32,10,98,14,24,65,86,91,68,80,51,99,96,88,7,57,17,67,98,56,89,88,95,69,80,25,64,90,60,67,92,39,42,32,57,73,0,37,68,38,87,69,92,38,9,29,89,98,71,41,86,59,61,74,6,5,98,28,66,76,33,3,45,61,24,86,80,25,97,64,15,20,94,13,25,98,39,5,30,22,23,9,9,28,4,18,40,71,38,71,25,93,99,61,99,15,69,82,96,43,24,61,3,49,76,26,52,88,16,73,36,81,74,14,40,38,35,13,52,51,38,92,40,7,1,38,5,94,64,54,14,5,15,99,34,48,2,30,1,58,68,24,51,79,67,42,95,0,23,81,25,88,41,36,13,13,78,75,26,31,41,93,63,30,63,93,92,0,35,30,77,79,81,89,80,36,14,58,92,45,3,61,70,63,91,42,60,66,92,11,88,47,27,63,57,9,81,46,35,10,53,13,94,58,1,35,98,16,83,83,96,35,37,93,83,39,39,11,54,28,75,87,23,73,81,48,52,11,41,56,10,92,5,11,68,48,25,7,63,75,61,12,21,96,16,34,47,49,67,55,38,32,63,17,56,71,90,12,69,55,62,12,77,14,8,25,39,76,60,84,4,0,30,67,96,4,55,30,39,81,54,55,75,46,44,30,58,0,38,79,37,50,36,9,80,84,75,50,51,88,19,18,24,1,49,46,48,95,2,18,53,77,83,1,41,71,57,76,28,85,82,7,99,36,99,66,65,75,78,40,6,95,37,87,50,79,54,59,89,29,48,87,30,78,11,57,8,14,35,72,29,73,51,79,59,49,23,1,95,88,25,47,10,79,35,5,23,18,7,78,68,27,28,95,48,63,40,72,4,29,20,0,56,13,69,1,39,43,95,38,35,26,83,1,94,9,80,10,69,99,1,84,12,54,47,27,6,77,3,9,28,22,23,26,15,34,75,57,98,35,59,44,54,42,65,0,84,79,94,78,63,66,46,79,89,32,40,63,67,74,95,30,40,79,75,56,86,46,76,64];
    let mut c = vec![15,94,17,69,96,60,50,18,36,82,54,76,43,19,7,66,37,93,43,64,51,42,8,83,51,53,74,69,0,74,30,89,21,97,92,5,28,41,27,21,52,50,15,8,62,2,90,29,14,27,13,57,74,95,64,41,96,55,12,89,4,43,17,87,20,27,46,68,65,61,25,56,33,3,36,78,4,65,44,72,74,51,85,83,35,84,28,50,18,82,51,27,90,92,37,31,45,31,3,28,98,85,76,91,74,77,46,3,21,97,50,23,64,94,68,44,50,60,9,41,12,6,72,71,70,15,18,79,38,77,58,31,91,78,63,65,56,67,22,98,34,17,15,22,75,3,84,12,75,7,37,58,14,76,8,54,79,95,45,55,32,24,11,41,19,21,51,68,77,73,66,57,9,69,3,41,84,68,46,51,21,29,8,28,48,99,32,47,63,98,27,54,88,34,36,73,92,87,86,1,15,7,87,9,29,16,86,99,33,66,62,90,40,41,44,25,75,32,48,29,16,99,49,90,10,78,86,8,48,22,76,3,51,53,59,13,57,16,96,3,50,29,96,37,74,83,86,53,92,87,48,27,35,78,59,72,29,11,60,11,78,52,71,57,96,42,94,95,96,35,72,79,59,65,28,76,83,22,55,48,92,69,64,6,3,36,19,27,88,51,55,32,33,92,6,6,77,6,8,73,29,76,56,24,12,73,74,13,48,74,35,76,79,55,53,52,5,48,92,10,17,91,85,49,99,40,97,2,42,32,97,27,75,44,84,45,20,42,61,46,79,59,55,20,25,26,66,76,43,17,98,66,49,81,78,75,86,21,66,16,14,40,70,93,85,4,53,80,23,80,35,35,96,7,41,70,99,13,70,47,53,3,32,45,12,41,8,22,34,11,50,30,73,99,8,3,45,59,49,77,7,82,80,97,93,15,10,76,15,27,25,0,96,62,49,40,48,78,7,87,96,23,43,12,25,85,49,26,63,87,79,55,72,14,78,21,31,84,96,64,14,46,23,95,37,1,72,34,30,99,98,73,98,8,77,1,6,32,83,12,62,67,13,32,17,73,13,65,79,35,15,30,26,51,33,85,15,63,89,19,10,47,21,81,35,62,40,51,45,52,53,54,13,91,98,95,29,36,18,16,73,65,88,11,23,68,47,60,32,65,17,45,24,87,82,67,6,55,98,29,8,0,6,91,76,44,67,12,38,16,10,78,50,68,26,11,48,43,15,17,11,25,91,88,40,73,74,77,43,55,26,37,53,96,40,98,51,3,72,2,97,52,1,30,1,34,3,95,8,88,55,23,64,90,66,71,97,81,73,49,56,26,3,60,88,27,69,62,19,97,71,50,28,54,81,99,91,28,99,68,0,62,0,9,55,77,10,48,55,9,46,50,26,88,81,86,73,3,53,18,35,68,59,68,27,17,61,98,91,11,72,81,24,92,64,78,14,88,90,27,36,48,24,7,33,10,68,65,19,91,38,54,69,27,62,17,27,1,7,23,38,57,39,49,43,95,38,78,59,29,21,6,31,74,16,75,96,25,60,38,53,59,64,59,81,65,11,90,61,80,0,92,39,5,70,25,58,36,31,82,43,98,23,26,43,75,19,92,30,71,24,10,43,70,57,44,61,60,78,23,60,35,71,38,63,59,20,57,97,56,12,95,29,87,45,93,47,66,1,39,68,49,82,96,35,30,49,64,97,34,96,16,71,93,97,77,45,29,89,49,93,10,73,2,10,75,26,90,82,59,54,44,1,73,45,17,47,15,63,51,47,61,78,6,83,35,6,8,77,70,69,67,22,28,63,86,84,7,63,3,60,6,52,24,43,20,73,28,79,13,79,42,57,29,57,80,67,43,44,99,63,57,84,69,96,42,27,50,24,6,19,29,12,53,17,95,8,50,48,42,92,25,13,27,77,3,87,4,93,66,27,79,13,65,7,7,8,66,56,72,69,18,52,76,27,6,22,73,81,11,56,70,0,82,21,85,38,88,90,75,67,13,9,87,61,97,7,4,52,52,72,77,12,94,9,67,58,1,93,70,32,41,52,15,14,9,94,93,40,90,9,54,83,93,14,32,20,53,8,95,57,69,52,76,31,27,78,67,87,25,76,34,92,80,63,14,1,66,23,89,67,72,7,75,86,56,93,36,30,21,22,95,7,99,10,29,97,30,67,90,31,78,12,94,33,35,11,84,97,85,35,68,37,40,77,70,28,55,40,22,98,2,65,1,18,82,8,42,48,98,76,63,2,0,48,76,20,8,63,13];
    let mut h = vec![39,72,46,44,19,77,88,46,78,98,79,73,42,89,5,62,27,69,96,60,77,32,24,10,75,51,4,32,13,8,88,79,23,16,11,81,20,60,68,65,21,46,96,7,64,11,76,22,14,19,48,30,49,37,78,89,80,90,30,19,63,86,76,86,21,52,87,76,10,100,53,39,51,39,87,95,62,7,61,64,51,74,30,88,99,47,13,84,42,76,17,48,53,71,34,73,82,19,12,21,50,25,96,93,8,94,80,95,46,53,77,87,66,82,85,66,56,85,100,100,55,38,57,100,45,17,45,13,48,20,100,61,70,51,9,47,41,45,47,30,21,48,93,24,27,38,15,28,53,45,17,50,82,58,23,87,29,27,96,100,27,90,68,55,96,21,62,68,94,52,3,28,45,6,89,43,11,97,100,94,51,55,17,47,31,66,25,78,83,39,76,43,63,52,42,7,91,81,24,83,69,55,39,79,80,80,34,17,25,91,81,98,34,11,94,44,4,82,14,11,45,31,67,95,19,48,12,99,72,33,18,54,26,13,92,15,14,13,61,49,88,93,47,69,8,4,99,84,80,77,15,56,96,60,49,20,32,70,22,12,54,26,31,9,47,65,50,10,19,78,81,51,30,84,53,77,38,21,28,70,14,4,90,77,100,52,91,93,50,31,56,34,97,65,17,39,92,92,31,19,70,52,84,42,46,7,26,96,40,96,85,38,79,48,11,16,99,17,58,38,63,80,4,6,54,38,49,18,16,40,100,11,35,64,30,80,90,99,47,65,74,96,10,50,4,75,72,14,5,56,22,43,34,71,8,51,50,99,79,90,81,20,24,100,74,77,21,4,73,58,78,9,89,3,50,92,22,79,36,43,26,55,84,34,41,88,86,84,93,98,4,22,96,7,94,25,48,62,8,49,70,67,88,90,65,56,26,55,40,81,69,43,16,48,55,47,3,73,9,16,76,92,40,42,61,50,33,84,46,99,76,4,22,23,36,58,10,18,87,88,25,36,42,70,90,47,69,95,19,97,71,91,74,29,70,14,23,5,15,30,88,24,12,3,85,40,44,45,13,5,69,8,70,7,95,89,94,77,82,4,80,8,60,23,10,83,24,7,31,39,54,25,89,59,73,10,44,86,36,46,49,91,96,47,12,78,12,21,92,10,39,58,42,13,85,42,97,28,67,58,19,35,88,69,70,78,34,66,73,86,97,33,71,67,88,38,83,25,61,21,11,15,66,9,58,18,60,95,60,56,73,93,95,5,52,40,60,27,42,14,47,16,95,3,73,69,18,76,55,89,72,69,38,4,73,95,88,24,57,74,67,86,98,48,39,67,83,92,91,70,40,12,5,24,76,28,69,68,9,53,95,69,6,34,80,86,4,89,89,48,47,60,85,6,32,48,36,42,93,4,22,60,57,70,6,56,31,37,88,74,49,96,100,81,22,43,57,61,22,28,96,12,6,6,77,72,80,72,30,23,90,4,100,80,73,13,26,5,36,75,35,67,82,60,96,74,95,44,76,36,66,76,89,33,12,73,60,70,50,27,21,89,86,56,7,97,60,87,58,47,17,15,73,72,19,12,70,75,71,53,78,34,52,96,63,88,92,100,90,84,37,17,15,52,16,66,4,11,57,5,43,100,80,6,70,27,47,66,5,13,87,10,26,25,2,53,16,60,38,88,25,8,47,48,29,75,59,71,22,88,85,14,59,65,37,89,22,21,51,89,71,5,23,36,17,37,64,60,5,16,14,87,23,21,5,7,30,56,94,81,54,57,86,88,69,80,59,34,97,4,31,93,38,58,92,95,76,81,46,52,21,38,96,37,95,55,10,78,77,98,71,43,22,12,97,87,60,24,35,29,43,23,97,26,60,68,47,19,80,67,66,4,40,60,71,4,46,6,10,46,24,67,34,67,70,95,24,96,51,85,9,54,85,92,81,46,6,40,68,20,63,85,63,64,71,47,75,74,87,68,59,68,85,12,29,19,67,74,55,10,32,94,39,23,60,70,86,11,10,43,41,69,34,92,29,43,91,11,52,59,34,23,19,66,33,5,51,56,63,19,98,34,4,40,84,57,48,44,40,5,39,86,88,99,70,36,50,8,30,96,6,24,74,26,18,36,61,5,37,16,6,75,37,97,30,6,55,97,16,24,80,7,38,25,7,89,30,89,66,81,90,67,52,73,28,9,95,42,61,20,17,65,49,4,98,30,80,14,100,50,57,69,4,3,13,26,44,30,12,87,39,65,69,18,60,82,60,68,100,36];
    let mut rng = XorShift::new(std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().subsec_nanos() as f64 as i64);
    random_solution(&mut rng, &mut a, &mut b, &mut r, &mut c, &mut h);
    let mut score = 0;
    for r in 0..N {
        for c in 0..N {
            score += (a[r][c] - b[r][c]).abs();
        }
    }
    let mut best_score = 1e9 as i32;
    let mut best_r = vec![0; M];
    let mut best_c = vec![0; M];
    let mut best_h = vec![0; M];
    if score < best_score {
        best_score = score;
        for i in 0..M {
            best_r[i] = r[i];
            best_c[i] = c[i];
            best_h[i] = h[i];
        }
    }
    eprintln!("{}", best_score);

    let mut cumsum_minus = vec![vec![0; N + 1]; N];
    let mut cumsum_plus = vec![vec![0; N + 1]; N];
    init_cumsum(&mut a, &mut b, &mut cumsum_minus, &mut cumsum_plus);

    simulated_annealing(&mut rng, &mut a, &mut b, &mut r, &mut c, &mut h, &mut cumsum_minus, &mut cumsum_plus);

    let mut row_index_set = vec![IntSet::new(M); N];
    let mut column_index_set = vec![IntSet::new(M); N];
    for i in 0..M {
        row_index_set[r[i] as usize].add(i);
        column_index_set[c[i] as usize].add(i);
    }

    simulated_annealing2(&mut rng, &mut a, &mut b, &mut r, &mut c, &mut h, &mut cumsum_minus, &mut cumsum_plus, &mut row_index_set, &mut column_index_set);
    let mut score_sa = 0;
    for r in 0..N {
        for c in 0..N {
            score_sa += (a[r][c] - b[r][c]).abs();
        }
    }
    if score_sa < best_score {
        best_score = score_sa;
        for i in 0..M {
            best_r[i] = r[i];
            best_c[i] = c[i];
            best_h[i] = h[i];
        }
    }
    eprintln!("{}", best_score);

    println!("{}", M);
    for i in 0..M {
        println!("{} {} {}", best_c[i], best_r[i], best_h[i]);
    }
}

struct XorShift {
    w: u32,
    x: u32,
    y: u32,
    z: u32,
}

impl XorShift {
    fn new(l: i64) -> Self {
        XorShift {
            x: l as u32,
            y: 362436069,
            z: 521288629,
            w: 88675123,
        }
    }

    fn next(&mut self) -> u32 {
        let t = self.x ^ (self.x << 11);
        self.x = self.y;
        self.y = self.z;
        self.z = self.w;
        self.w = self.w ^ (self.w >> 19) ^ (t ^ (t >> 8));
        self.w
    }

    fn next_double(&mut self) -> f64 {
        (self.next() >> 1) as f64 * 4.6566128730773926e-10
    }
}

fn random_solution(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>) {
    for i in 0..M {
        update(b, r[i], c[i], h[i]);
    }
}

fn update(b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32) {
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2);
        let max_c = N_1.min(c0 + dc2);
        for c in min_c..=max_c {
            b[r as usize][c as usize] += h0 - ((r - r0).abs() + (c - c0).abs());
        }
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2);
        let max_c = N_1.min(c0 + dc2);
        for c in min_c..=max_c {
            b[r as usize][c as usize] += h0 - ((r - r0).abs() + (c - c0).abs());
        }
        dc2 += -1;
    }
}

fn simulated_annealing(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    // let start_time = get_time();
    // let end_time = 1.0;
    let start_time = 0.0;
    let end_time = 60000.0;
    let start_temperature = 35.0;
    let end_temperature = 35.0;
    let mask = (1 << 10) - 1;
    let mut time = start_time;
    let mut temperature = start_temperature;
    let mut num_iterations: usize = 0;
    loop {
        num_iterations += 1;
        if (num_iterations & mask) == 0 {
            // time = get_time();
            time = num_iterations as f64;
            temperature = 1.0 / (start_temperature + (end_temperature - start_temperature) * (time - start_time) / (end_time - start_time));
            if time > end_time {
                let mut score = 0;
                for i in 0..N {
                    for j in 0..N {
                        score += (a[i][j] - b[i][j]).abs();
                    }
                }
                eprintln!("num_iterations : {}, score : {}, temperature : {}, time : {}", num_iterations, score, 1.0 / temperature, time);
                    break;
            }
        }

        let random = (rng.next_double() * 6.0) as i32;
        match random {
            0 => row_minus(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, num_iterations),
            1 => row_plus(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, num_iterations),
            2 => column_minus(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, num_iterations),
            3 => column_plus(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, num_iterations),
            4 => height_minus(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, num_iterations),
            5 => height_plus(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, num_iterations),
            _ => {},
        }
    }
}

fn simulated_annealing2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>) {
    let start_time = get_time();
    let end_time = 5.98;
    let start_temperature = 35.0;
    let end_temperature = 0.0;
    let mask = (1 << 10) - 1;
    let mut time = start_time;
    let mut temperature = start_temperature;
    let mut num_iterations: usize = 0;
    loop {
        num_iterations += 1;
        if (num_iterations & mask) == 0 {
            time = get_time();
            temperature = 1.0 / (start_temperature + (end_temperature - start_temperature) * (time - start_time) / (end_time - start_time));
            if time > end_time {
                let mut score = 0;
                for i in 0..N {
                    for j in 0..N {
                        score += (a[i][j] - b[i][j]).abs();
                    }
                }
                eprintln!("num_iterations : {}, score : {}, temperature : {}, time : {}", num_iterations, score, 1.0 / temperature, time);
                    break;
            }
        }

        let random = (rng.next_double() * 6.0) as i32;
        match random {
            0 => row_minus2(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, row_index_set, column_index_set, num_iterations),
            1 => row_plus2(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, row_index_set, column_index_set, num_iterations),
            2 => column_minus2(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, row_index_set, column_index_set, num_iterations),
            3 => column_plus2(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, row_index_set, column_index_set, num_iterations),
            4 => height_minus2(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, row_index_set, column_index_set, num_iterations),
            5 => height_plus2(rng, a, b, r, c, h, cumsum_minus, cumsum_plus, temperature, row_index_set, column_index_set, num_iterations),
            _ => {},
        }
    }
}

fn row_minus(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index = num_iterations % M;
    if r[index] == 0 {
        return;
    }
    let delta_score = delta_score_row_minus(r[index], c[index], h[index], cumsum_minus, cumsum_plus);
    if accept(delta_score, temperature, rng) {
        update_row_minus(a, b, r[index], c[index], h[index], cumsum_minus, cumsum_plus);
        r[index] += -1;
    }
}

fn row_minus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index1 = num_iterations % M;
    if r[index1] == 0 {
        return;
    }
    let r1 = r[index1];
    let c1 = c[index1];
    let h1 = h[index1];
    let set = &row_index_set[(r1 - 1) as usize];
    let has = set.size() > 0;
    let index2 = if !has {0} else {set.get((set.size() as f64 * rng.next_double()) as usize)};
    let r2 = r[index2];
    let c2 = c[index2];
    let h2 = h[index2];
    if has && h1 >= h2 + (c2 - c1).abs() {
        let delta_score1 = delta_score_row_minus(r1, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_row_minus(r1, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score1 - delta_score2, temperature, rng) {
            update_row_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_row_plus (a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            row_index_set[r1 as usize].remove(index1);
            row_index_set[r2 as usize].remove(index2);
            r[index1] += -1;
            r[index2] += 1;
            row_index_set[r1 as usize - 1].add(index1);
            row_index_set[r2 as usize + 1].add(index2);
        }
    } else if has && h2 >= h1 + (c2 - c1).abs() {
        let delta_score1 = delta_score_row_plus(r2, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_row_plus(r2, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score2 - delta_score1, temperature, rng) {
            update_row_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_row_plus (a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            row_index_set[r1 as usize].remove(index1);
            row_index_set[r2 as usize].remove(index2);
            r[index1] += -1;
            r[index2] += 1;
            row_index_set[r1 as usize - 1].add(index1);
            row_index_set[r2 as usize + 1].add(index2);
        }
    } else {
        let delta_score = delta_score_row_minus(r1, c1, h1, cumsum_minus, cumsum_plus);
        if accept(delta_score, temperature, rng) {
            update_row_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            row_index_set[r1 as usize].remove(index1);
            r[index1] += -1;
            row_index_set[r1 as usize - 1].add(index1);
        }
    }
}

fn row_plus(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index = num_iterations % M;
    if r[index] == N_1 {
        return;
    }
    let delta_score = delta_score_row_plus(r[index], c[index], h[index], cumsum_minus, cumsum_plus);
    if accept(delta_score, temperature, rng) {
        update_row_plus(a, b, r[index], c[index], h[index], cumsum_minus, cumsum_plus);
        r[index] += 1;
    }
}

fn row_plus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index1 = num_iterations % M;
    if r[index1] == N_1 {
        return;
    }
    let r1 = r[index1];
    let c1 = c[index1];
    let h1 = h[index1];
    let set = &row_index_set[(r1 + 1) as usize];
    let has = set.size() > 0;
    let index2 = if !has {0} else {set.get((set.size() as f64 * rng.next_double()) as usize)};
    let r2 = r[index2];
    let c2 = c[index2];
    let h2 = h[index2];
    if has && h1 >= h2 + (c2 - c1).abs() {
        let delta_score1 = delta_score_row_plus(r1, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_row_plus(r1, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score1 - delta_score2, temperature, rng) {
            update_row_plus (a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_row_minus(a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            row_index_set[r1 as usize].remove(index1);
            row_index_set[r2 as usize].remove(index2);
            r[index1] += 1;
            r[index2] += -1;
            row_index_set[r1 as usize + 1].add(index1);
            row_index_set[r2 as usize - 1].add(index2);
        }
    } else if has && h2 >= h1 + (c2 - c1).abs() {
        let delta_score1 = delta_score_row_minus(r2, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_row_minus(r2, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score2 - delta_score1, temperature, rng) {
            update_row_plus (a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_row_minus(a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            row_index_set[r1 as usize].remove(index1);
            row_index_set[r2 as usize].remove(index2);
            r[index1] += 1;
            r[index2] += -1;
            row_index_set[r1 as usize + 1].add(index1);
            row_index_set[r2 as usize - 1].add(index2);
        }
    } else {
        let delta_score = delta_score_row_plus(r1, c1, h1, cumsum_minus, cumsum_plus);
        if accept(delta_score, temperature, rng) {
            update_row_plus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            row_index_set[r1 as usize].remove(index1);
            r[index1] += 1;
            row_index_set[r1 as usize + 1].add(index1);
        }
    }
}

fn column_minus(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index = num_iterations % M;
    if c[index] == 0 {
        return;
    }
    let delta_score = delta_score_column_minus(r[index], c[index], h[index], cumsum_minus, cumsum_plus);
    if accept(delta_score, temperature, rng) {
        update_column_minus(a, b, r[index], c[index], h[index], cumsum_minus, cumsum_plus);
        c[index] += -1;
    }
}

fn column_minus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index1 = num_iterations % M;
    if c[index1] == 0 {
        return;
    }
    let r1 = r[index1];
    let c1 = c[index1];
    let h1 = h[index1];
    let set = &column_index_set[(c1 - 1) as usize];
    let has = set.size() > 0;
    let index2 = if !has {0} else {set.get((set.size() as f64 * rng.next_double()) as usize)};
    let r2 = r[index2];
    let c2 = c[index2];
    let h2 = h[index2];
    if has && h1 >= h2 + (r2 - r1).abs() {
        let delta_score1 = delta_score_column_minus(r1, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_column_minus(r2, c1, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score1 - delta_score2, temperature, rng) {
            update_column_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_column_plus (a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            column_index_set[c1 as usize].remove(index1);
            column_index_set[c2 as usize].remove(index2);
            c[index1] += -1;
            c[index2] += 1;
            column_index_set[c1 as usize - 1].add(index1);
            column_index_set[c2 as usize + 1].add(index2);
        }
    } else if has && h2 >= h1 + (r2 - r1).abs() {
        let delta_score1 = delta_score_column_plus(r1, c2, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_column_plus(r2, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score2 - delta_score1, temperature, rng) {
            update_column_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_column_plus (a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            column_index_set[c1 as usize].remove(index1);
            column_index_set[c2 as usize].remove(index2);
            c[index1] += -1;
            c[index2] += 1;
            column_index_set[c1 as usize - 1].add(index1);
            column_index_set[c2 as usize + 1].add(index2);
        }
    } else {
        let delta_score = delta_score_column_minus(r1, c1, h1, cumsum_minus, cumsum_plus);
        if accept(delta_score, temperature, rng) {
            update_column_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            column_index_set[c1 as usize].remove(index1);
            c[index1] += -1;
            column_index_set[c1 as usize - 1].add(index1);
        }
    }
}

fn column_plus(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index = num_iterations % M;
    if c[index] == N_1 {
        return;
    }
    let delta_score = delta_score_column_plus(r[index], c[index], h[index], cumsum_minus, cumsum_plus);
    if accept(delta_score, temperature, rng) {
        update_column_plus(a, b, r[index], c[index], h[index], cumsum_minus, cumsum_plus);
        c[index] += 1;
    }
}

fn column_plus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index1 = num_iterations % M;
    if c[index1] == N_1 {
        return;
    }
    let r1 = r[index1];
    let c1 = c[index1];
    let h1 = h[index1];
    let set = &column_index_set[(c1 + 1) as usize];
    let has = set.size() > 0;
    let index2 = if !has {0} else {set.get((set.size() as f64 * rng.next_double()) as usize)};
    let r2 = r[index2];
    let c2 = c[index2];
    let h2 = h[index2];
    if has && h1 >= h2 + (r2 - r1).abs() {
        let delta_score1 = delta_score_column_plus(r1, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_column_plus(r2, c1, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score1 - delta_score2, temperature, rng) {
            update_column_plus (a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_column_minus(a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            column_index_set[c1 as usize].remove(index1);
            column_index_set[c2 as usize].remove(index2);
            c[index1] += 1;
            c[index2] += -1;
            column_index_set[c1 as usize + 1].add(index1);
            column_index_set[c2 as usize - 1].add(index2);
        }
    } else if has && h2 >= h1 + (r2 - r1).abs() {
        let delta_score1 = delta_score_column_minus(r1, c2, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_column_minus(r2, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score2 - delta_score1, temperature, rng) {
            update_column_plus (a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_column_minus(a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            column_index_set[c1 as usize].remove(index1);
            column_index_set[c2 as usize].remove(index2);
            c[index1] += 1;
            c[index2] += -1;
            column_index_set[c1 as usize + 1].add(index1);
            column_index_set[c2 as usize - 1].add(index2);
        }
    } else {
        let delta_score = delta_score_column_plus(r1, c1, h1, cumsum_minus, cumsum_plus);
        if accept(delta_score, temperature, rng) {
            update_column_plus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            column_index_set[c1 as usize].remove(index1);
            c[index1] += 1;
            column_index_set[c1 as usize + 1].add(index1);
        }
    }
}

fn height_minus(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index = num_iterations % M;
    if h[index] == 1 {
        return;
    }
    let delta_score = delta_score_height_minus(r[index], c[index], h[index], cumsum_minus, cumsum_plus);
    if accept(delta_score, temperature, rng) {
        update_height_minus(a, b, r[index], c[index], h[index], cumsum_minus, cumsum_plus);
        h[index] += -1;
    }
}

fn height_minus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index1 = num_iterations % M;
    if h[index1] == 1 {
        return;
    }
    let r1 = r[index1];
    let c1 = c[index1];
    let h1 = h[index1];
    let set = if rng.next_double() < 0.5 {&row_index_set   [0.max((N-1).min((r1 - 3 + (7.0 * rng.next_double()) as i32) as usize))]}
                                            else {&column_index_set[0.max((N-1).min((c1 - 3 + (7.0 * rng.next_double()) as i32) as usize))]};
    let has = set.size() > 0;
    let index2 = if !has {0} else {set.get((set.size() as f64 * rng.next_double()) as usize)};
    let r2 = r[index2];
    let c2 = c[index2];
    let h2 = h[index2];
    if has && h2 <= 99 && h1 >= 1 + h2 + (r2 - r1).abs() + (c2 - c1).abs() {
        let delta_score1 = delta_score_height_minus(r1, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_height_minus(r2, c2, h2 + 1, cumsum_minus, cumsum_plus);
        if accept(delta_score1 - delta_score2, temperature, rng) {
            update_height_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_height_plus (a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            h[index1] += -1;
            h[index2] += 1;
        }
    } else if has && h2 <= 99 && index2 != index1 && h2 + 1 >= h1 + (r2 - r1).abs() + (c2 - c1).abs() {
        let delta_score1 = delta_score_height_plus(r1, c1, h1 - 1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_height_plus(r2, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score2 - delta_score1, temperature, rng) {
            update_height_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_height_plus (a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            h[index1] += -1;
            h[index2] += 1;
        }
    } else {
        let delta_score = delta_score_height_minus(r1, c1, h1, cumsum_minus, cumsum_plus);
        if accept(delta_score, temperature, rng) {
            update_height_minus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            h[index1] += -1;
        }
    }
}

fn height_plus(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index = num_iterations % M;
    if h[index] == 100 {
        return;
    }
    let delta_score = delta_score_height_plus(r[index], c[index], h[index], cumsum_minus, cumsum_plus);
    if accept(delta_score, temperature, rng) {
        update_height_plus(a, b, r[index], c[index], h[index], cumsum_minus, cumsum_plus);
        h[index] += 1;
    }
}

fn height_plus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    // let index = (rng.next_double() * M as f64) as usize;
    let index1 = num_iterations % M;
    if h[index1] == 100 {
        return;
    }
    let r1 = r[index1];
    let c1 = c[index1];
    let h1 = h[index1];
    let set = if rng.next_double() < 0.5 {&row_index_set   [0.max((N-1).min((r1 - 3 + (7.0 * rng.next_double()) as i32) as usize))]}
                                            else {&column_index_set[0.max((N-1).min((c1 - 3 + (7.0 * rng.next_double()) as i32) as usize))]};
    let has = set.size() > 0;
    let index2 = if !has {0} else {set.get((set.size() as f64 * rng.next_double()) as usize)};
    let r2 = r[index2];
    let c2 = c[index2];
    let h2 = h[index2];
    if has && index2 != index1 && h2 >= 2 && h1 + 1 >= h2 + (r2 - r1).abs() + (c2 - c1).abs() {
        let delta_score1 = delta_score_height_plus(r1, c1, h1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_height_plus(r2, c2, h2 - 1, cumsum_minus, cumsum_plus);
        if accept(delta_score1 - delta_score2, temperature, rng) {
            update_height_plus (a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_height_minus(a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            h[index1] += 1;
            h[index2] += -1;
        }
    } else if has && h2 >= 2 && h2 >= 1 + h1 + (r2 - r1).abs() + (c2 - c1).abs() {
        let delta_score1 = delta_score_height_minus(r1, c1, h1 + 1, cumsum_minus, cumsum_plus);
        let delta_score2 = delta_score_height_minus(r2, c2, h2, cumsum_minus, cumsum_plus);
        if accept(delta_score2 - delta_score1, temperature, rng) {
            update_height_plus (a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            update_height_minus(a, b, r2, c2, h2, cumsum_minus, cumsum_plus);
            h[index1] += 1;
            h[index2] += -1;
        }
    } else {
        let delta_score = delta_score_height_plus(r1, c1, h1, cumsum_minus, cumsum_plus);
        if accept(delta_score, temperature, rng) {
            update_height_plus(a, b, r1, c1, h1, cumsum_minus, cumsum_plus);
            h[index1] += 1;
        }
    }
}

fn init_cumsum(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    for r in 0..N {
        init_cumsum_r(r, 0, a, b, cumsum_minus, cumsum_plus);
    }
}

fn init_cumsum_r(r: usize, c0: usize, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    for c in c0..N {
        cumsum_minus[r][c + 1] = cumsum_minus[r][c] + (if b[r][c] > a[r][c] {-1} else {1});
        cumsum_plus[r][c + 1] = cumsum_plus[r][c] + (if b[r][c] < a[r][c] {-1} else {1});
    }
}

fn sum_minus(r: usize, min_c: usize, max_c: usize, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    return cumsum_minus[r][max_c + 1] - cumsum_minus[r][min_c];
}

fn sum_plus(r: usize, min_c: usize, max_c: usize, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    return cumsum_plus[r][max_c + 1] - cumsum_plus[r][min_c];
}

fn accept(delta_score: i32, temperature: f64, rng: &mut XorShift) -> bool {
    if delta_score <= 0 {
        return true;
    }
    let d = -delta_score as f64 * temperature;
    if d < -10.0 {
        return false;
    }
    return LOG[rng.next() as usize & 127] < d;
}

fn delta_score_row_minus(r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    let mut delta_score = 0;
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2 - 1);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - (r0 - 1)).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_plus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_minus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
    return delta_score;
}

fn update_row_minus(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2 - 1);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - (r0 - 1)).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += 1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += -1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
}

fn delta_score_row_plus(r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    let mut delta_score = 0;
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2 + 1);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..=r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_minus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0 + 1..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_plus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
    return delta_score;
}

fn update_row_plus(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2 + 1);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..=r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += -1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0 + 1..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += 1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
}

fn delta_score_column_minus(r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    let mut delta_score = 0;
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2 - 1);
        let max_c = N_1.min(c0 + dc2);
        delta_score += sum_plus(r as usize, min_c as usize, (c0 - 1) as usize, cumsum_minus, cumsum_plus);
        delta_score += sum_minus(r as usize, c0 as usize, max_c as usize, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2 - 1);
        let max_c = N_1.min(c0 + dc2);
        delta_score += sum_plus(r as usize, min_c as usize, (c0 - 1) as usize, cumsum_minus, cumsum_plus);
        delta_score += sum_minus(r as usize, c0 as usize, max_c as usize, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
    return delta_score;
}

fn update_column_minus(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2 - 1) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=(c0 - 1) as usize {
            b[r as usize][c] += 1;
        }
        for c in c0 as usize..=max_c {
            b[r as usize][c] += -1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2 - 1) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=(c0 - 1) as usize {
            b[r as usize][c] += 1;
        }
        for c in c0 as usize..=max_c {
            b[r as usize][c] += -1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
}

fn delta_score_column_plus(r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    let mut delta_score = 0;
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2 + 1) as usize;
        delta_score += sum_minus(r as usize, min_c, c0 as usize, cumsum_minus, cumsum_plus);
        delta_score += sum_plus(r as usize, (c0 + 1) as usize, max_c, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2 + 1) as usize;
        delta_score += sum_minus(r as usize, min_c, c0 as usize, cumsum_minus, cumsum_plus);
        delta_score += sum_plus(r as usize, (c0 + 1) as usize, max_c, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
    return delta_score;
}

fn update_column_plus(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2 + 1) as usize;
        for c in min_c..=c0 as usize {
            b[r as usize][c] += -1;
        }
        for c in (c0 + 1) as usize..=max_c {
            b[r as usize][c] += 1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2 + 1) as usize;
        for c in min_c..=c0 as usize {
            b[r as usize][c] += -1;
        }
        for c in (c0 + 1) as usize..=max_c {
            b[r as usize][c] += 1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
}

fn delta_score_height_minus(r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    let mut delta_score = 0;
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_minus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_minus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
    return delta_score;
}

fn update_height_minus(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    let h2 = h0 - 1;
    let min_r = 0.max(r0 - h2);
    let max_r = N_1.min(r0 + h2);
    let mut dc2 = h2 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += -1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h2;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += -1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
}

fn delta_score_height_plus(r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) -> i32 {
    let mut delta_score = 0;
    let min_r = 0.max(r0 - h0);
    let max_r = N_1.min(r0 + h0);
    let mut dc2 = h0 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_plus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h0;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        delta_score += sum_plus(r as usize, min_c, max_c, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
    return delta_score;
}

fn update_height_plus(a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r0: i32, c0: i32, h0: i32, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>) {
    let min_r = 0.max(r0 - h0);
    let max_r = N_1.min(r0 + h0);
    let mut dc2 = h0 - (min_r - r0).abs();
    for r in min_r..r0 {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += 1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += 1;
    }
    dc2 = h0;
    for r in r0..=max_r {
        let min_c = 0.max(c0 - dc2) as usize;
        let max_c = N_1.min(c0 + dc2) as usize;
        for c in min_c..=max_c {
            b[r as usize][c] += 1;
        }
        init_cumsum_r(r as usize, min_c, a, b, cumsum_minus, cumsum_plus);
        dc2 += -1;
    }
}

#[derive(Clone)]
struct IntSet {
    empty: usize,
    size: usize,
    index_to_value: Vec<usize>,
    value_to_index: Vec<usize>,
}

impl IntSet {
    fn new(capacity: usize) -> IntSet {
        IntSet {
            empty: capacity,
            size: 0,
            index_to_value: vec![0; capacity],
            value_to_index: vec![capacity; capacity],
        }
    }

    fn add(&mut self, value: usize) -> bool {
        if self.value_to_index[value] != self.empty {
            return false;
        }

        self.index_to_value[self.size] = value;
        self.value_to_index[value] = self.size;
        self.size += 1;
        return true;
    }

    fn remove(&mut self, value: usize) -> bool {
        let index = self.value_to_index[value];
        if index == self.empty {
            return false;
        }
        self.remove_by_index(index);
        true
    }

    fn remove_by_index(&mut self, index: usize) -> bool {
        if self.size == 0 {
            return false;
        }

        // assert!(index < self.size);
        self.size -= 1;

        let value = self.index_to_value[index];
        let value2 = self.index_to_value[self.size];

        self.index_to_value[index] = value2;
        self.value_to_index[value2 as usize] = index;
        self.index_to_value[self.size] = value;
        self.value_to_index[value as usize] = self.empty;
        true
    }

    fn get(&self, index: usize) -> usize {
        // assert!(index < self.size);
        self.index_to_value[index]
    }

    fn size(&self) -> usize {
        self.size
    }
}

impl std::fmt::Display for IntSet {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let slice = &self.index_to_value[0..self.size];
        write!(f, "{:?}", slice)
    }
}

提出情報

コンパイルエラー

warning: unused variable: `rng`
   --> src/main.rs:119:20
    |
119 | fn random_solution(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>) {
    |                    ^^^ help: consider prefixing with an underscore: `_rng`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `a`
   --> src/main.rs:119:40
    |
119 | fn random_solution(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>) {
    |                                        ^ help: consider prefixing with an underscore: `_a`

warning: value assigned to `time` is never read
   --> src/main.rs:157:13
    |
157 |     let mut time = start_time;
    |             ^^^^
    |
    = note: `#[warn(unused_assignments)]` on by default
    = help: maybe it is overwritten before being read?

warning: value assigned to `time` is never read
   --> src/main.rs:197:13
    |
197 |     let mut time = start_time;
    |             ^^^^
    |
    = help: maybe it is overwritten before being read?

warning: unused variable: `column_index_set`
   --> src/main.rs:243:253
    |
243 | fn row_minus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut Vec<i32>, h: &mut Vec<i32>, cumsum_minus: &mut Vec<Vec<i32>>, cumsum_plus: &mut Vec<Vec<i32>>, temperature: f64, row_index_set: &mut Vec<IntSet>, column_index_set: &mut Vec<IntSet>, num_iterations: usize) {
    |                                                                                                                                                                                                                                                             ^^^^^^^^^^^^^^^^ help: consider prefixing with an underscore: `_column_index_set`

warning: unused variable: `column_index_set`
   --> src/main.rs:308:252
    |
308 | fn row_plus2(rng: &mut XorShift, a: &mut Vec<Vec<i32>>, b: &mut Vec<Vec<i32>>, r: &mut Vec<i32>, c: &mut V...

ジャッジ結果