#1169519 (Rust) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: assy1028
• 提出日時: 2026-06-21 12:30:24
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 972 ms / 1,000 ms
• コード長: 14,490 bytes
• コンパイル時間: 2,531 ms
• コンパイル使用メモリ: 208,208 KB
• 実行使用メモリ: 6,400 KB
• スコア: 43,937
• 最終ジャッジ日時: 2026-06-21 12:31:01
• 合計ジャッジ時間: 35,792 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 32

ソースコード

use std::io::{self, Read};
use std::time::Instant;

const TIME_LIMIT_SEC: f64 = 0.97;
const TRIPLE_RATE_PERCENT: usize = 100;

#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct Stick {
    y: usize,
    x: usize,
    vertical: bool,
}

#[derive(Clone)]
struct Solution {
    moves: Vec<Stick>,
    residual: Vec<i32>,
    score: i32,
}

struct XorShift {
    x: u64,
}

impl XorShift {
    fn new(seed: u64) -> Self {
        let mut x = seed.wrapping_add(0x9e3779b97f4a7c15);
        x ^= x >> 30;
        x = x.wrapping_mul(0xbf58476d1ce4e5b9);
        x ^= x >> 27;
        x = x.wrapping_mul(0x94d049bb133111eb);
        x ^= x >> 31;
        Self { x }
    }

    fn next_u64(&mut self) -> u64 {
        let mut x = self.x;
        x ^= x << 7;
        x ^= x >> 9;
        self.x = x;
        x
    }

    fn gen_usize(&mut self, upper: usize) -> usize {
        ((self.next_u64() as u128 * upper as u128) >> 64) as usize
    }

    fn shuffle<T>(&mut self, a: &mut [T]) {
        for i in (1..a.len()).rev() {
            let j = self.gen_usize(i + 1);
            a.swap(i, j);
        }
    }
}

fn elapsed_sec(start: Instant) -> f64 {
    start.elapsed().as_secs_f64()
}

fn is_time_left(start: Instant) -> bool {
    elapsed_sec(start) < TIME_LIMIT_SEC
}

fn apply_stick(residual: &mut [i32], n: usize, stick: Stick, len: usize) -> i32 {
    let mut delta = 0;
    if stick.vertical {
        let x = stick.x;
        for dy in 0..len {
            let idx = (stick.y + dy) * n + x;
            delta += residual[idx];
            residual[idx] = -residual[idx];
        }
    } else {
        let row = stick.y * n;
        for dx in 0..len {
            let idx = row + stick.x + dx;
            delta += residual[idx];
            residual[idx] = -residual[idx];
        }
    }
    delta
}

fn best_stick(residual: &[i32], n: usize, len: usize) -> (i32, Stick) {
    let mut best = i32::MIN;
    let mut best_stick = Stick {
        y: 0,
        x: 0,
        vertical: false,
    };

    for y in 0..n {
        let row = y * n;
        let mut sum = 0;
        for dx in 0..len {
            sum += residual[row + dx];
        }
        if sum > best {
            best = sum;
            best_stick = Stick {
                y,
                x: 0,
                vertical: false,
            };
        }
        for x in 1..=n - len {
            sum += residual[row + x + len - 1] - residual[row + x - 1];
            if sum > best {
                best = sum;
                best_stick = Stick {
                    y,
                    x,
                    vertical: false,
                };
            }
        }
    }

    if len > 1 {
        for x in 0..n {
            let mut sum = 0;
            for dy in 0..len {
                sum += residual[dy * n + x];
            }
            if sum > best {
                best = sum;
                best_stick = Stick {
                    y: 0,
                    x,
                    vertical: true,
                };
            }
            for y in 1..=n - len {
                sum += residual[(y + len - 1) * n + x] - residual[(y - 1) * n + x];
                if sum > best {
                    best = sum;
                    best_stick = Stick {
                        y,
                        x,
                        vertical: true,
                    };
                }
            }
        }
    }

    (best, best_stick)
}

fn random_stick(rng: &mut XorShift, n: usize, len: usize) -> Stick {
    let vertical = len > 1 && rng.gen_usize(2) == 0;
    if vertical {
        Stick {
            y: rng.gen_usize(n - len + 1),
            x: rng.gen_usize(n),
            vertical: true,
        }
    } else {
        Stick {
            y: rng.gen_usize(n),
            x: rng.gen_usize(n - len + 1),
            vertical: false,
        }
    }
}

fn greedy_solution(weights: &[i32], n: usize, lengths: &[usize], order: &[usize]) -> Solution {
    let mut residual = weights.to_vec();
    let mut moves = vec![Stick::default(); lengths.len()];
    let mut score = 0;
    for &idx in order {
        let len = lengths[idx];
        let (delta, stick) = best_stick(&residual, n, len);
        score += delta;
        apply_stick(&mut residual, n, stick, len);
        moves[idx] = stick;
    }
    Solution {
        moves,
        residual,
        score,
    }
}

fn rebuild_solution(weights: &[i32], n: usize, lengths: &[usize], moves: &[Stick]) -> Solution {
    let mut residual = weights.to_vec();
    let mut score = 0;
    for i in 0..lengths.len() {
        score += apply_stick(&mut residual, n, moves[i], lengths[i]);
    }
    Solution {
        moves: moves.to_vec(),
        residual,
        score,
    }
}

fn improve_one(solution: &mut Solution, n: usize, lengths: &[usize], idx: usize) -> bool {
    let before = solution.score;
    let old = solution.moves[idx];
    let len = lengths[idx];
    solution.score += apply_stick(&mut solution.residual, n, old, len);
    let (delta, new_stick) = best_stick(&solution.residual, n, len);
    solution.score += delta;
    apply_stick(&mut solution.residual, n, new_stick, len);
    solution.moves[idx] = new_stick;
    solution.score > before
}

fn coordinate_descent(
    solution: &mut Solution,
    n: usize,
    lengths: &[usize],
    rng: &mut XorShift,
    start: Instant,
) {
    let k = lengths.len();
    let mut order: Vec<usize> = (0..k).collect();
    let mut sweep = 0;
    while is_time_left(start) {
        if sweep & 1 == 0 {
            order.sort_by_key(|&i| std::cmp::Reverse(lengths[i]));
        } else {
            rng.shuffle(&mut order);
        }
        let mut improved = 0;
        for &idx in &order {
            if !is_time_left(start) {
                return;
            }
            if improve_one(solution, n, lengths, idx) {
                improved += 1;
            }
        }
        sweep += 1;
        if improved == 0 && sweep >= 2 {
            break;
        }
    }
}

fn improve_pair(
    solution: &mut Solution,
    n: usize,
    lengths: &[usize],
    i: usize,
    j: usize,
    rng: &mut XorShift,
) -> bool {
    if i == j {
        return false;
    }
    let before_score = solution.score;
    let old_i = solution.moves[i];
    let old_j = solution.moves[j];
    let len_i = lengths[i];
    let len_j = lengths[j];

    solution.score += apply_stick(&mut solution.residual, n, old_i, len_i);
    solution.score += apply_stick(&mut solution.residual, n, old_j, len_j);

    let first_i = rng.gen_usize(2) == 0;
    if first_i {
        let (delta_i, new_i) = best_stick(&solution.residual, n, len_i);
        solution.score += delta_i;
        apply_stick(&mut solution.residual, n, new_i, len_i);
        let (delta_j, new_j) = best_stick(&solution.residual, n, len_j);
        solution.score += delta_j;
        apply_stick(&mut solution.residual, n, new_j, len_j);
        solution.moves[i] = new_i;
        solution.moves[j] = new_j;
    } else {
        let (delta_j, new_j) = best_stick(&solution.residual, n, len_j);
        solution.score += delta_j;
        apply_stick(&mut solution.residual, n, new_j, len_j);
        let (delta_i, new_i) = best_stick(&solution.residual, n, len_i);
        solution.score += delta_i;
        apply_stick(&mut solution.residual, n, new_i, len_i);
        solution.moves[i] = new_i;
        solution.moves[j] = new_j;
    }

    if solution.score > before_score {
        true
    } else {
        apply_stick(&mut solution.residual, n, solution.moves[j], len_j);
        apply_stick(&mut solution.residual, n, solution.moves[i], len_i);
        solution.score = before_score;
        solution.moves[i] = old_i;
        solution.moves[j] = old_j;
        apply_stick(&mut solution.residual, n, old_i, len_i);
        apply_stick(&mut solution.residual, n, old_j, len_j);
        false
    }
}

fn improve_triple(
    solution: &mut Solution,
    n: usize,
    lengths: &[usize],
    i: usize,
    j: usize,
    h: usize,
    rng: &mut XorShift,
) -> bool {
    if i == j || i == h || j == h {
        return false;
    }

    let inds = [i, j, h];
    let before_score = solution.score;
    let old = [
        solution.moves[inds[0]],
        solution.moves[inds[1]],
        solution.moves[inds[2]],
    ];

    for t in 0..3 {
        let idx = inds[t];
        solution.score += apply_stick(&mut solution.residual, n, old[t], lengths[idx]);
    }

    let mut order = [0usize, 1, 2];
    for t in (1..3).rev() {
        let p = rng.gen_usize(t + 1);
        order.swap(t, p);
    }

    let mut new_sticks = [Stick::default(); 3];
    for &t in &order {
        let idx = inds[t];
        let (delta, stick) = best_stick(&solution.residual, n, lengths[idx]);
        solution.score += delta;
        apply_stick(&mut solution.residual, n, stick, lengths[idx]);
        new_sticks[t] = stick;
    }

    if solution.score > before_score {
        for t in 0..3 {
            solution.moves[inds[t]] = new_sticks[t];
        }
        true
    } else {
        for &t in order.iter().rev() {
            let idx = inds[t];
            apply_stick(&mut solution.residual, n, new_sticks[t], lengths[idx]);
        }
        solution.score = before_score;
        for t in 0..3 {
            let idx = inds[t];
            solution.moves[idx] = old[t];
            apply_stick(&mut solution.residual, n, old[t], lengths[idx]);
        }
        false
    }
}

fn build_close_indices(lengths: &[usize]) -> Vec<Vec<usize>> {
    let k = lengths.len();
    let mut by_len = vec![Vec::new(); 26];
    for (i, &len) in lengths.iter().enumerate() {
        by_len[len].push(i);
    }

    let mut close = vec![Vec::new(); k];
    for i in 0..k {
        let len = lengths[i];
        let lo = len.saturating_sub(3).max(1);
        let hi = (len + 3).min(25);
        for ll in lo..=hi {
            for &j in &by_len[ll] {
                if i != j {
                    close[i].push(j);
                }
            }
        }
    }
    close
}

fn perturb_and_reoptimize(
    best: &mut Solution,
    weights: &[i32],
    n: usize,
    lengths: &[usize],
    rng: &mut XorShift,
    start: Instant,
) {
    let k = lengths.len();
    let mut current = best.clone();
    while is_time_left(start) {
        let mut trial_moves = current.moves.clone();
        let changes = 4 + rng.gen_usize(9);
        for _ in 0..changes {
            let idx = rng.gen_usize(k);
            trial_moves[idx] = random_stick(rng, n, lengths[idx]);
        }
        let mut trial = rebuild_solution(weights, n, lengths, &trial_moves);
        coordinate_descent(&mut trial, n, lengths, rng, start);
        if trial.score > best.score {
            *best = trial.clone();
        }
        if trial.score >= current.score || rng.gen_usize(100) < 12 {
            current = trial;
        }
    }
}

fn make_initial_orders(lengths: &[usize], rng: &mut XorShift) -> Vec<Vec<usize>> {
    let k = lengths.len();
    let base: Vec<usize> = (0..k).collect();
    let mut orders = Vec::new();

    orders.push(base.clone());

    let mut desc = base.clone();
    desc.sort_by_key(|&i| std::cmp::Reverse(lengths[i]));
    orders.push(desc);

    let mut asc = base.clone();
    asc.sort_by_key(|&i| lengths[i]);
    orders.push(asc);

    for _ in 0..10 {
        let mut random = base.clone();
        rng.shuffle(&mut random);
        orders.push(random);
    }

    orders
}

fn solve(n: usize, lengths: &[usize], weights: &[i32]) -> Solution {
    let start = Instant::now();
    let mut seed = 0x123456789abcdef0u64;
    for (i, &v) in weights.iter().enumerate() {
        if v > 0 {
            seed ^= (i as u64 + 1).wrapping_mul(0x9e3779b97f4a7c15);
        }
    }
    for (i, &l) in lengths.iter().enumerate() {
        seed ^= ((l as u64) << (i % 17)).wrapping_mul(0xbf58476d1ce4e5b9);
    }
    let mut rng = XorShift::new(seed);

    let orders = make_initial_orders(lengths, &mut rng);
    let mut best = greedy_solution(weights, n, lengths, &orders[0]);

    for order in orders {
        if !is_time_left(start) {
            break;
        }
        let mut candidate = greedy_solution(weights, n, lengths, &order);
        coordinate_descent(&mut candidate, n, lengths, &mut rng, start);
        if candidate.score > best.score {
            best = candidate;
        }
    }

    let close_indices = build_close_indices(lengths);
    let mut local_trials = 0;
    while is_time_left(start) && local_trials < 100_000 {
        let i = rng.gen_usize(lengths.len());
        let j = if rng.gen_usize(100) < 85 && !close_indices[i].is_empty() {
            close_indices[i][rng.gen_usize(close_indices[i].len())]
        } else {
            rng.gen_usize(lengths.len())
        };
        if rng.gen_usize(100) < TRIPLE_RATE_PERCENT && !close_indices[i].is_empty() {
            let h = close_indices[i][rng.gen_usize(close_indices[i].len())];
            improve_triple(&mut best, n, lengths, i, j, h, &mut rng);
        } else {
            improve_pair(&mut best, n, lengths, i, j, &mut rng);
        }
        local_trials += 1;
    }

    perturb_and_reoptimize(&mut best, weights, n, lengths, &mut rng, start);
    best
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let k: usize = it.next().unwrap().parse().unwrap();
    let mut lengths = Vec::with_capacity(k);
    for _ in 0..k {
        lengths.push(it.next().unwrap().parse::<usize>().unwrap());
    }

    let mut weights = vec![0; n * n];
    for y in 0..n {
        let row = it.next().unwrap().as_bytes().to_vec();
        for x in 0..n {
            weights[y * n + x] = if row[x] == b'1' { 1 } else { -1 };
        }
    }

    let solution = solve(n, &lengths, &weights);
    let mut out = String::new();
    for i in 0..k {
        let len = lengths[i];
        let stick = solution.moves[i];
        if stick.vertical {
            out.push_str(&format!(
                "{} {} {} {}\n",
                stick.y + 1,
                stick.x + 1,
                stick.y + len,
                stick.x + 1
            ));
        } else {
            out.push_str(&format!(
                "{} {} {} {}\n",
                stick.y + 1,
                stick.x + 1,
                stick.y + 1,
                stick.x + len
            ));
        }
    }
    print!("{out}");
}