Submission #2576771


Source Code Expand

Copy
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::io::{Write, Stderr};
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;
use std::time::{Duration, SystemTime, Instant};

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! println_stderr {
    ($($arg:tt)*) => { {
        let r = writeln!(&mut ::std::io::stderr(), $($arg)*);
        r.expect("failed printing to stderr");
    } }
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

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

impl XorShift {
    fn new() -> XorShift {
        XorShift {
            x: 123456789,
            y: 362436069,
            z: 521288629,
            w: 88675123
        }
    }

    fn rotate(&mut self) {
        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));
    }

    fn next_int(&mut self, n: usize) -> usize {
        self.rotate();
        let r = (self.w as i32) % (n as i32);
        if r < 0 {
            (r + n as i32) as usize
        } else {
            r as usize
        }
    }
}

// ===

type TheMap = Vec<Vec<i32>>;

const N: usize = 100;
const Q: usize = 1000;
const TIMEOUT_MILLIS: u64 = 5800;

struct Operation {
    x: usize,
    y: usize,
    h: usize
}

struct GlobalState {
    start_time: Instant,
    random: XorShift,
    map: TheMap
}

impl GlobalState {
    fn exec(&mut self) {
        let timeout = Duration::from_millis(TIMEOUT_MILLIS);
        let mut tried = 0;
        let mut best_operations: Vec<Operation> = vec![];
        let mut best_map = vec![vec![0; N]; N];
        for _ in 0..Q {
            let op = self.generate();
            apply(&mut best_map, &op, 1);
            best_operations.push(op)
        }
        let mut best_score = diff(&self.map, &best_map);

        loop {
            if self.start_time.elapsed() > timeout {
                break;
            }
            tried += 1;
            let (ith, newop, score) = self.doit(&best_operations, &mut best_map);
            if best_score > score {
                best_score = score;
                apply(&mut best_map, &best_operations[ith], -1);
                apply(&mut best_map, &newop, 1);
                best_operations[ith] = newop;
            }
        }

        println_stderr!("tries: {}", tried);
        println_stderr!("score: {}", best_score);

        println!("{}", best_operations.len());
        for op in best_operations {
            println!("{} {} {}", op.x, op.y, op.h);
        }
    }


    fn generate(&mut self) -> Operation {
        Operation {
            x: self.random.next_int(N),
            y: self.random.next_int(N),
            h: self.random.next_int(N)+1
        }
    }

    fn doit(&mut self, base_operations: &Vec<Operation>, base_map: &mut TheMap) -> (usize, Operation, u64) {
        let ith = self.random.next_int(Q);
        let mut newop = self.generate();

        newop.x = self.tweak(base_operations[ith].x, 0, N-1);
        newop.y = self.tweak(base_operations[ith].y, 0, N-1);
        newop.h = self.tweak(base_operations[ith].h, 1, N);

        apply(base_map, &base_operations[ith], -1);
        apply(base_map, &newop, 1);

        let sc = diff(&self.map, &base_map);

        apply(base_map, &newop, -1);
        apply(base_map, &base_operations[ith], 1);

        (ith, newop, sc)
    }

    fn tweak(&mut self, v: usize, min: usize, max: usize) -> usize {
        if v == min {
            if self.random.next_int(2) == 0 {
                return v + 1;
            }
            v
        } else if v == max {
            if self.random.next_int(2) == 0 {
                return v - 1;
            }
            v
        } else {
            v + self.random.next_int(3) - 1
        }
    }
}


fn apply(map: &mut TheMap, op: &Operation, sign: i32) {
    let cy: i32 = op.y as i32;
    let cx: i32 = op.x as i32;
    let h: i32 = op.h as i32;
    for y in cy-h..cy+h+1 {
        if y < 0 || y >= N as i32 {
            continue
        }
        for x in cx-h..cx+h+1 {
            if x < 0 || x >= N as i32 {
                continue
            }
            let diff = (cy-y).abs() + (cx-x).abs();
            if diff >= h {
                continue
            }
            map[y as usize][x as usize] += (h - diff) * sign;
        }
    }
}

fn diff(map: &TheMap, rmap: &TheMap) -> u64 {
    let mut cost: u64 = 0;
    for i in 0..N {
        for j in 0..N {
            cost += (map[i][j] - rmap[i][j]).abs() as u64;
        }
    }
    cost
}

fn score(map: &TheMap, ops: &Vec<Operation>) -> u64 {
    let mut rmap = vec![vec![0; N]; N];
    for op in ops {
        apply(&mut rmap, &op, 1);
    }

    let mut cost: u64 = 0;
    for i in 0..N {
        for j in 0..N {
            cost += (map[i][j] - rmap[i][j]).abs() as u64;
        }
    }
    cost
}

fn main() {
    let start_time = Instant::now();

    let mut random = XorShift::new();
    let mut map: TheMap = vec![vec![]; N];
    for i  in 0..N {
        map[i] = readnc();
    }
    GlobalState { start_time: start_time, random: random, map: map }.exec();
}

Submission Info

Submission Time
Task A - 山型足し算
User hamadu
Language Rust (1.15.1)
Score 9997577965
Code Size 6465 Byte
Status AC
Exec Time 5804 ms
Memory 4476 KB

Compile Error

warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
   --> ./Main.rs:258:9
    |
258 |     let mut random = XorShift::new();
    |         ^^^^^^^^^^

Judge Result

Set Name Sample All
Score / Max Score 199950196 / 200000000 9797627769 / 9800000000
Status
AC × 1
AC × 49
Set Name Test Cases
Sample example_01.txt
All subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt, subtask_01_31.txt, subtask_01_32.txt, subtask_01_33.txt, subtask_01_34.txt, subtask_01_35.txt, subtask_01_36.txt, subtask_01_37.txt, subtask_01_38.txt, subtask_01_39.txt, subtask_01_40.txt, subtask_01_41.txt, subtask_01_42.txt, subtask_01_43.txt, subtask_01_44.txt, subtask_01_45.txt, subtask_01_46.txt, subtask_01_47.txt, subtask_01_48.txt, subtask_01_49.txt
Case Name Status Exec Time Memory
example_01.txt AC 5804 ms 4352 KB
subtask_01_01.txt AC 5804 ms 4352 KB
subtask_01_02.txt AC 5804 ms 4352 KB
subtask_01_03.txt AC 5804 ms 4352 KB
subtask_01_04.txt AC 5804 ms 4352 KB
subtask_01_05.txt AC 5804 ms 4352 KB
subtask_01_06.txt AC 5804 ms 4352 KB
subtask_01_07.txt AC 5804 ms 4352 KB
subtask_01_08.txt AC 5804 ms 4352 KB
subtask_01_09.txt AC 5804 ms 4352 KB
subtask_01_10.txt AC 5804 ms 4352 KB
subtask_01_11.txt AC 5804 ms 4352 KB
subtask_01_12.txt AC 5804 ms 4352 KB
subtask_01_13.txt AC 5804 ms 4352 KB
subtask_01_14.txt AC 5804 ms 4352 KB
subtask_01_15.txt AC 5804 ms 4352 KB
subtask_01_16.txt AC 5804 ms 4352 KB
subtask_01_17.txt AC 5804 ms 4352 KB
subtask_01_18.txt AC 5804 ms 4352 KB
subtask_01_19.txt AC 5804 ms 4352 KB
subtask_01_20.txt AC 5804 ms 4352 KB
subtask_01_21.txt AC 5804 ms 4352 KB
subtask_01_22.txt AC 5804 ms 4352 KB
subtask_01_23.txt AC 5804 ms 4352 KB
subtask_01_24.txt AC 5804 ms 4352 KB
subtask_01_25.txt AC 5804 ms 4352 KB
subtask_01_26.txt AC 5804 ms 4352 KB
subtask_01_27.txt AC 5804 ms 4352 KB
subtask_01_28.txt AC 5804 ms 4352 KB
subtask_01_29.txt AC 5804 ms 4352 KB
subtask_01_30.txt AC 5804 ms 4352 KB
subtask_01_31.txt AC 5804 ms 4352 KB
subtask_01_32.txt AC 5804 ms 4352 KB
subtask_01_33.txt AC 5804 ms 4352 KB
subtask_01_34.txt AC 5804 ms 4352 KB
subtask_01_35.txt AC 5804 ms 4352 KB
subtask_01_36.txt AC 5804 ms 4476 KB
subtask_01_37.txt AC 5804 ms 4352 KB
subtask_01_38.txt AC 5804 ms 4352 KB
subtask_01_39.txt AC 5804 ms 4352 KB
subtask_01_40.txt AC 5804 ms 4352 KB
subtask_01_41.txt AC 5804 ms 4352 KB
subtask_01_42.txt AC 5804 ms 4476 KB
subtask_01_43.txt AC 5804 ms 4352 KB
subtask_01_44.txt AC 5804 ms 4352 KB
subtask_01_45.txt AC 5804 ms 4352 KB
subtask_01_46.txt AC 5804 ms 4352 KB
subtask_01_47.txt AC 5804 ms 4352 KB
subtask_01_48.txt AC 5804 ms 4352 KB
subtask_01_49.txt AC 5804 ms 4352 KB