Submission #46859980

---

Source Code Expand

pub mod action {
    use crate::def::*;
    use crate::interactor::*;
    use crate::util::*;

    fn select_lighter_item(group: &Vec<usize>, balancer: &mut Balancer) -> usize {
        let item_idx_in_group = rnd::gen_range(0, group.len());
        let item_idx = group[item_idx_in_group];
        let item_idx = balancer.find_lighter_in_group(item_idx, &group);
        item_idx
    }

    pub fn action_move(
        heavier_g_idx: usize,
        lighter_g_idx: usize,
        groups: &mut Vec<Vec<usize>>,
        rank: &mut Vec<usize>,
        input: &Input,
        balancer: &mut Balancer,
        interactor: &mut Interactor,
    ) -> bool {
        let item_idx = select_lighter_item(&groups[rank[heavier_g_idx]], balancer);
        let i = groups[rank[heavier_g_idx]]
            .iter()
            .position(|x| *x == item_idx)
            .unwrap();
        groups[rank[heavier_g_idx]].swap_remove(i);

        // 集合の重さの差が改善しなければ不採用
        match balancer.get_result(
            &groups[rank[lighter_g_idx]],
            &groups[rank[heavier_g_idx]],
            interactor,
        ) {
            BalanceResult::Right | BalanceResult::Equal => {
                groups[rank[heavier_g_idx]].push(item_idx);
                return false;
            }
            _ => {}
        }

        let prev_g_idx = rank[heavier_g_idx];
        if !update_rank(
            rank,
            &groups,
            true,
            lighter_g_idx,
            heavier_g_idx,
            input,
            interactor,
            balancer,
        ) {
            // 計測できなかった場合はとりあえず元に戻す
            groups[prev_g_idx].push(item_idx);
            // rankは更新できなかったが、moveは成功している
            return true;
        }
        groups[rank[lighter_g_idx]].push(item_idx);
        if !update_rank(
            rank,
            &groups,
            false,
            lighter_g_idx,
            heavier_g_idx,
            input,
            interactor,
            balancer,
        ) {
            // rankは更新できなかったが、moveは成功している
            return true;
        }

        true
    }

    pub fn action_swap(
        heavier_g_idx: usize,
        lighter_g_idx: usize,
        groups: &mut Vec<Vec<usize>>,
        rank: &mut Vec<usize>,
        input: &Input,
        balancer: &mut Balancer,
        interactor: &mut Interactor,
    ) -> bool {
        let item_idx_a = select_lighter_item(&groups[rank[lighter_g_idx]], balancer);
        let item_idx_b = select_lighter_item(&groups[rank[heavier_g_idx]], balancer);

        // 入れ替えようとしているアイテムの大小関係が集合の大小関係と一致しなければ不採用
        match balancer.get_result(&vec![item_idx_a], &vec![item_idx_b], interactor) {
            BalanceResult::Left | BalanceResult::Equal => {}
            _ => return false,
        }

        let i = groups[rank[lighter_g_idx]]
            .iter()
            .position(|x| *x == item_idx_a)
            .unwrap();
        groups[rank[lighter_g_idx]].swap_remove(i);
        let i = groups[rank[heavier_g_idx]]
            .iter()
            .position(|x| *x == item_idx_b)
            .unwrap();
        groups[rank[heavier_g_idx]].swap_remove(i);
        match balancer.get_result(
            &groups[rank[lighter_g_idx]],
            &groups[rank[heavier_g_idx]],
            interactor,
        ) {
            // 集合の重さの差が悪化したら不採用
            BalanceResult::Right | BalanceResult::Unknown => {
                groups[rank[lighter_g_idx]].push(item_idx_a);
                groups[rank[heavier_g_idx]].push(item_idx_b);
                return false;
            }
            _ => {
                let to_idx = rank[lighter_g_idx];
                groups[rank[heavier_g_idx]].push(item_idx_a);
                if !update_rank(
                    rank,
                    &groups,
                    true,
                    lighter_g_idx,
                    heavier_g_idx,
                    input,
                    interactor,
                    balancer,
                ) {
                    // 最後に更新できなかった場合、変更先に更新する
                    groups[to_idx].push(item_idx_b);
                    // rankは更新できなかったが、swapは成功している
                    return true;
                }
                groups[rank[lighter_g_idx]].push(item_idx_b);
                if !update_rank(
                    rank,
                    &groups,
                    false,
                    lighter_g_idx,
                    heavier_g_idx,
                    input,
                    interactor,
                    balancer,
                ) {
                    // rankは更新できなかったが、swapは成功している
                    return true;
                }
                return true;
            }
        }
    }

    ///
    /// 1. A < Bとする
    /// 2. A、Bからランダムにアイテムa_1, b_1を選択する
    /// 3. a_1 > b_1の時
    ///     1. a_1 < b_1 + b_2となるようにアイテムb_2をBから選択する
    /// 4. a_1 < b_1の時
    ///     1. a_1 + a_2 < b_1となるようなa_2があればAから選択する
    ///
    /// NOTE: trial_count = 0にすればaction_swapと一緒の挙動？
    ///
    pub fn action_swap2(
        heavier_g_idx: usize,
        lighter_g_idx: usize,
        groups: &mut Vec<Vec<usize>>,
        rank: &mut Vec<usize>,
        input: &Input,
        balancer: &mut Balancer,
        interactor: &mut Interactor,
    ) -> bool {
        const TRIAL_COUNT: usize = 3;
        let mut item_indices_a =
            vec![groups[rank[lighter_g_idx]][rnd::gen_range(0, groups[rank[lighter_g_idx]].len())]];
        let mut item_indices_b =
            vec![groups[rank[heavier_g_idx]][rnd::gen_range(0, groups[rank[heavier_g_idx]].len())]];

        // 入れ替えようとしているアイテムの大小関係が集合の大小関係と一致しなければ不採用
        match balancer.get_result(&item_indices_a, &item_indices_b, interactor) {
            BalanceResult::Right => {
                // 重い方に大小関係が入れ替わるものがあれば足す
                for _ in 0..TRIAL_COUNT {
                    let b2 = select_lighter_item(&groups[rank[heavier_g_idx]], balancer);
                    if item_indices_b.contains(&b2) {
                        continue;
                    }
                    item_indices_b.push(b2);
                    match balancer.get_result(&item_indices_a, &item_indices_b, interactor) {
                        BalanceResult::Left | BalanceResult::Equal => break,
                        _ => {
                            item_indices_b.pop();
                        }
                    }
                }
            }
            BalanceResult::Left => {
                // 軽い方に足せるものがあれば足す
                for _ in 0..TRIAL_COUNT {
                    let a2 = select_lighter_item(&groups[rank[lighter_g_idx]], balancer);
                    if item_indices_a.contains(&a2) {
                        continue;
                    }
                    item_indices_a.push(a2);
                    match balancer.get_result(&item_indices_a, &item_indices_b, interactor) {
                        BalanceResult::Left | BalanceResult::Equal => continue,
                        _ => {
                            item_indices_a.pop();
                        }
                    }
                }
            }
            BalanceResult::Equal => {}
            BalanceResult::Unknown => return false,
        }
        match balancer.get_result(&item_indices_a, &item_indices_b, interactor) {
            BalanceResult::Left | BalanceResult::Equal => {}
            _ => return false,
        }

        for item_idx_a in item_indices_a.iter() {
            let i = groups[rank[lighter_g_idx]]
                .iter()
                .position(|e| e == item_idx_a)
                .unwrap();
            groups[rank[lighter_g_idx]].remove(i);
        }
        for item_idx_b in item_indices_b.iter() {
            let i = groups[rank[heavier_g_idx]]
                .iter()
                .position(|e| e == item_idx_b)
                .unwrap();
            groups[rank[heavier_g_idx]].remove(i);
        }

        match balancer.get_result(
            &groups[rank[lighter_g_idx]],
            &groups[rank[heavier_g_idx]],
            interactor,
        ) {
            // 集合の重さの差が悪化したら不採用
            BalanceResult::Right | BalanceResult::Unknown => {
                for item_idx_a in item_indices_a.iter() {
                    groups[rank[lighter_g_idx]].push(*item_idx_a);
                }
                for item_idx_b in item_indices_b.iter() {
                    groups[rank[heavier_g_idx]].push(*item_idx_b);
                }
                return false;
            }
            _ => {
                let to_idx = rank[lighter_g_idx];
                for item_idx_a in item_indices_a.iter() {
                    groups[rank[heavier_g_idx]].push(*item_idx_a);
                }
                if !update_rank(
                    rank,
                    &groups,
                    true,
                    lighter_g_idx,
                    heavier_g_idx,
                    input,
                    interactor,
                    balancer,
                ) {
                    for item_idx_b in item_indices_b.iter() {
                        groups[to_idx].push(*item_idx_b);
                    }
                    // rankは更新できなかったが、swapは成功している
                    return true;
                }
                for item_idx_b in item_indices_b.iter() {
                    groups[rank[lighter_g_idx]].push(*item_idx_b);
                }
                if !update_rank(
                    rank,
                    &groups,
                    false,
                    lighter_g_idx,
                    heavier_g_idx,
                    input,
                    interactor,
                    balancer,
                ) {
                    // rankは更新できなかったが、swapは成功している
                    return true;
                }
                if item_indices_a.len() > 1 || item_indices_b.len() > 1 {
                    eprintln!("swap2: {:?} {:?}", item_indices_a, item_indices_b);
                }
                return true;
            }
        }
    }
}
pub mod def {
    pub const TIME_LIMIT: f64 = 2.0;

    use crate::interactor::*;
    use crate::util::*;

    #[derive(Debug)]
    pub struct Input {
        pub n: usize,
        pub d: usize,
        pub q: usize,
    }

    #[derive(PartialEq, Eq, Debug, Clone, Copy)]
    pub enum BalanceResult {
        Left,    // <
        Right,   // >
        Equal,   // =
        Unknown, // failed to get result (query limit or search failure)
    }

    pub struct Balancer {
        pub left_edges: FastHashMap<u128, Vec<u128>>, // first <= second
        pub right_edges: FastHashMap<u128, Vec<u128>>, // first > second
        pub cached_results: FastHashMap<(u128, u128), BalanceResult>,
    }

    impl Balancer {
        pub fn new() -> Balancer {
            Balancer {
                left_edges: FastHashMap::default(),
                right_edges: FastHashMap::default(),
                cached_results: FastHashMap::default(),
            }
        }

        ///
        /// 1. 部分集合が存在するかチェックし、存在するなら辺を引く
        /// 2. 差分が1個の集合が存在するかチェックし、存在し、かつ差分の大小関係がわかっているものに対して辺を引く
        /// 3. 元の位置から探索を開始する
        ///
        pub fn get_result(
            &mut self,
            left_v: &Vec<usize>,
            right_v: &Vec<usize>,
            interactor: &mut Interactor,
        ) -> BalanceResult {
            let check_empty_result = self.check_empty_comparison(left_v, right_v);
            if check_empty_result != BalanceResult::Unknown {
                return check_empty_result;
            }
            assert!(left_v.len() > 0 && right_v.len() > 0);

            let left_hash = self.to_hash(left_v);
            let right_hash = self.to_hash(right_v);

            if let Some(cached_result) = self.cached_results.get(&(left_hash, right_hash)) {
                return *cached_result;
            }

            self.add_additional_edges(left_hash);
            self.add_additional_edges(right_hash);

            let search_result = self.search_result(left_hash, right_hash);
            match search_result {
                BalanceResult::Unknown => {}
                BalanceResult::Left | BalanceResult::Equal => {
                    self.cached_results
                        .insert((left_hash, right_hash), BalanceResult::Left);
                    self.cached_results
                        .insert((right_hash, left_hash), BalanceResult::Right);
                    return search_result;
                }
                BalanceResult::Right => {
                    self.cached_results
                        .insert((right_hash, left_hash), BalanceResult::Left);
                    self.cached_results
                        .insert((left_hash, right_hash), BalanceResult::Right);
                    return search_result;
                }
            }
            let query_result = interactor.output_query(left_v, right_v);

            match query_result {
                BalanceResult::Left | BalanceResult::Equal => {
                    add_edge(&mut self.left_edges, left_hash, right_hash);
                    add_edge(&mut self.right_edges, right_hash, left_hash);
                }
                BalanceResult::Right => {
                    add_edge(&mut self.left_edges, right_hash, left_hash);
                    add_edge(&mut self.right_edges, left_hash, right_hash);
                }
                BalanceResult::Unknown => {}
            }
            query_result
        }

        fn search_result(&self, left_hash: u128, right_hash: u128) -> BalanceResult {
            // NOTE: left = rightの時は稀（だと思う）ので、ここでは無視している
            const MAX_DEPTH: u16 = 5;

            fn is_reachable(
                edges: &FastHashMap<u128, Vec<u128>>,
                from_hash: u128,
                to_hash: u128,
            ) -> bool {
                let mut q = Queue::default();
                let mut seen = FastHashSet::default();
                q.push_back((from_hash, 0));
                seen.insert(from_hash);
                while let Some((v, depth)) = q.pop_front() {
                    let Some(v_edges) = edges.get(&v) else { continue };
                    for u in v_edges {
                        if seen.contains(u) {
                            continue;
                        }
                        if *u == to_hash {
                            return true;
                        }
                        if depth >= MAX_DEPTH {
                            continue;
                        }
                        seen.insert(*u);
                        q.push_back((*u, depth + 1));
                    }
                }
                false
            }

            if is_reachable(&self.left_edges, left_hash, right_hash) {
                return BalanceResult::Left;
            } else if is_reachable(&self.right_edges, left_hash, right_hash) {
                return BalanceResult::Right;
            }
            BalanceResult::Unknown
        }

        pub fn find_lighter_in_group(&self, v: usize, groups: &Vec<usize>) -> usize {
            let mut q = vec![];
            let mut seen = FastHashSet::default();
            let group_hash = self.to_hash(groups);
            let v_hash = 1 << v;
            q.push((v_hash, 0));
            seen.insert(v_hash);

            let mut lightest_v = v_hash;
            let mut lightest_depth = 0;

            while let Some((v, depth)) = q.pop() {
                let Some(edges) = self.right_edges.get(&v) else { continue };
                for u in edges {
                    if seen.contains(u) {
                        continue;
                    }
                    if u.count_ones() == 1 && (u & group_hash) > 0 && depth > lightest_depth {
                        lightest_depth = depth;
                        lightest_v = *u;
                    }
                    q.push((*u, depth + 1));
                    seen.insert(*u);
                }
            }

            lightest_v.trailing_zeros() as usize
        }

        ///
        /// 1. 部分集合が存在するかチェックし、存在するなら辺を引く
        /// 2. 差分が1個の集合が存在するかチェックし、存在し、かつ差分の大小関係がわかっているものに対して辺を引く
        ///
        fn add_additional_edges(&mut self, v_hash: u128) {
            let mut additional_edges = vec![]; // first < second
            let edge_data = [&self.left_edges, &self.right_edges];
            for edges in edge_data {
                if edges.contains_key(&v_hash) {
                    continue;
                }
                for (u_hash, _) in edges.iter() {
                    // 部分集合のチェック
                    if (v_hash & *u_hash) == *u_hash {
                        additional_edges.push((*u_hash, v_hash));
                        continue;
                    }
                    if (v_hash & *u_hash) == v_hash {
                        additional_edges.push((v_hash, *u_hash));
                        continue;
                    }

                    // 差分が1個のものをチェック
                    // 包含しているパターンは前まででチェックできている
                    // v = 010111
                    // u = 001111
                    // v ^ u = 011000
                    // a = v & u = 000111
                    // v ^ a = 010000, u ^ a = 001000
                    if (v_hash ^ *u_hash).count_ones() == 2 {
                        let a = v_hash & *u_hash;
                        if let Some(cached_result) = self.cached_results.get(&(v_hash ^ a, *u_hash ^ a))
                        {
                            match cached_result {
                                BalanceResult::Left | BalanceResult::Equal => {
                                    additional_edges.push((v_hash, *u_hash));
                                }
                                BalanceResult::Right => {
                                    additional_edges.push((*u_hash, v_hash));
                                }
                                _ => {}
                            }
                        } else {
                            match self.search_result(v_hash ^ a, *u_hash ^ a) {
                                BalanceResult::Left | BalanceResult::Equal => {
                                    additional_edges.push((v_hash, *u_hash));
                                }
                                BalanceResult::Right => {
                                    additional_edges.push((*u_hash, v_hash));
                                }
                                _ => {}
                            }
                        }
                    }
                }
            }

            // NOTE: add_edgeで重複は考慮されるので、ここで取り除く必要はない
            for (left_hash, right_hash) in additional_edges {
                add_edge(&mut self.left_edges, left_hash, right_hash);
                add_edge(&mut self.right_edges, right_hash, left_hash);
            }
        }

        fn check_empty_comparison(&self, left_v: &Vec<usize>, right_v: &Vec<usize>) -> BalanceResult {
            if left_v.len() == 0 && right_v.len() > 0 {
                return BalanceResult::Left;
            } else if left_v.len() > 0 && right_v.len() == 0 {
                return BalanceResult::Right;
            } else if left_v.len() == 0 && right_v.len() == 0 {
                return BalanceResult::Equal;
            }
            BalanceResult::Unknown
        }

        fn to_hash(&self, v: &Vec<usize>) -> u128 {
            let mut hash = 0;
            for e in v.iter() {
                hash |= self.hash(*e);
            }
            hash
        }

        fn hash(&self, v: usize) -> u128 {
            1 << v
        }

        #[allow(unused)]
        pub fn print_edges(&self) {
            let mut edges_mean = 0.;
            for (_, edges) in self.left_edges.iter() {
                edges_mean += edges.len() as f64;
            }
            edges_mean /= self.left_edges.len() as f64;
            eprintln!(
                "left_edges_node: {}, right_edges_node: {}, edges_per_node: {}, cached_result_size: {}",
                self.left_edges.len(),
                self.right_edges.len(),
                edges_mean,
                self.cached_results.len()
            );
        }
    }

    fn add_edge(edges: &mut FastHashMap<u128, Vec<u128>>, first_hash: u128, second_hash: u128) {
        if let Some(current_edges) = edges.get_mut(&first_hash) {
            if !current_edges.contains(&second_hash) {
                current_edges.push(second_hash);
            }
        } else {
            edges.insert(first_hash, vec![second_hash]);
        }
    }

    pub fn groups_to_output_d(groups: &Vec<Vec<usize>>, input: &Input) -> Vec<usize> {
        let mut d = vec![0; input.n];
        for (g_idx, group) in groups.iter().enumerate() {
            for e in group {
                d[*e] = g_idx;
            }
        }
        d
    }

    pub fn sort_groups(
        groups: &Vec<Vec<usize>>,
        input: &Input,
        interactor: &mut Interactor,
        balancer: &mut Balancer,
    ) -> Vec<usize> {
        fn q_sort(
            targets: Vec<usize>,
            groups: &Vec<Vec<usize>>,
            input: &Input,
            interactor: &mut Interactor,
            balancer: &mut Balancer,
        ) -> Vec<usize> {
            if targets.len() <= 1 {
                return targets;
            }
            let pivot_g_idx = targets[rnd::gen_range(0, targets.len())];
            let mut left_targets = vec![pivot_g_idx];
            let mut right_targets = vec![];
            for g_idx in targets {
                if g_idx == pivot_g_idx {
                    continue;
                }
                match balancer.get_result(&groups[pivot_g_idx], &groups[g_idx], interactor) {
                    BalanceResult::Left => right_targets.push(g_idx), // <
                    BalanceResult::Right => left_targets.push(g_idx), // >
                    BalanceResult::Equal => right_targets.push(g_idx), // =
                    BalanceResult::Unknown => break,
                }
            }
            [
                q_sort(left_targets, groups, input, interactor, balancer),
                q_sort(right_targets, groups, input, interactor, balancer),
            ]
            .concat()
        }

        q_sort(
            (0..groups.len()).collect(),
            groups,
            input,
            interactor,
            balancer,
        )
    }

    pub fn update_rank(
        rank: &mut Vec<usize>,
        groups: &Vec<Vec<usize>>,
        from_up: bool,
        lighter_g_idx: usize,
        heaviest_g_idx: usize,
        input: &Input,
        interactor: &mut Interactor,
        balancer: &mut Balancer,
    ) -> bool {
        const PAR: usize = 8; // :param
        if input.d < PAR {
            update_rank_linear_search(
                rank,
                groups,
                from_up,
                lighter_g_idx,
                heaviest_g_idx,
                interactor,
                balancer,
            )
        } else {
            update_rank_binary_search(
                rank,
                groups,
                from_up,
                lighter_g_idx,
                heaviest_g_idx,
                interactor,
                balancer,
            )
        }
    }

    pub fn update_rank_linear_search(
        rank: &mut Vec<usize>,
        groups: &Vec<Vec<usize>>,
        from_up: bool,
        lighter_g_idx: usize,
        heavier_g_idx: usize,
        interactor: &mut Interactor,
        balancer: &mut Balancer,
    ) -> bool {
        if from_up {
            for i in (lighter_g_idx..heavier_g_idx).rev() {
                match balancer.get_result(&groups[rank[i]], &groups[rank[i + 1]], interactor) {
                    BalanceResult::Left => break,                // <
                    BalanceResult::Right => rank.swap(i, i + 1), // >
                    BalanceResult::Equal => break,               // =
                    BalanceResult::Unknown => return false,
                }
            }
        } else {
            for i in lighter_g_idx..heavier_g_idx {
                match balancer.get_result(&groups[rank[i]], &groups[rank[i + 1]], interactor) {
                    BalanceResult::Left => break,                // <
                    BalanceResult::Right => rank.swap(i, i + 1), // >
                    BalanceResult::Equal => break,               // =
                    BalanceResult::Unknown => return false,
                }
            }
        }
        true
    }

    pub fn update_rank_binary_search(
        rank: &mut Vec<usize>,
        groups: &Vec<Vec<usize>>,
        from_up: bool,
        lighter_g_idx: usize,
        heavier_g_idx: usize,
        interactor: &mut Interactor,
        balancer: &mut Balancer,
    ) -> bool {
        let move_g_idx = if from_up {
            heavier_g_idx
        } else {
            lighter_g_idx
        };
        let move_g = rank[move_g_idx];
        rank.remove(move_g_idx);
        let mut l = lighter_g_idx as i32 - 1;
        let mut r = heavier_g_idx as i32;
        while r - l > 1 {
            let m = (l + r) / 2;
            match balancer.get_result(&groups[rank[m as usize]], &groups[move_g], interactor) {
                BalanceResult::Left | BalanceResult::Equal => l = m, // <
                BalanceResult::Right => r = m,                       // >
                BalanceResult::Unknown => {
                    rank.insert(move_g_idx, move_g);
                    return false;
                }
            }
        }
        rank.insert(r as usize, move_g);
        true
    }
}
pub mod interactor {
    use crate::def::*;
    use std::io::{Stdin, Write};

    use proconio::*;

    pub struct Interactor {
        source: proconio::source::line::LineSource<std::io::BufReader<Stdin>>,
        pub query_count: usize,
        max_query_count: usize,
    }

    impl Interactor {
        pub fn new() -> Interactor {
            Interactor {
                source: proconio::source::line::LineSource::new(std::io::BufReader::new(
                    std::io::stdin(),
                )),
                query_count: 0,
                max_query_count: 1,
            }
        }

        pub fn read_input(&mut self) -> Input {
            input! {
                from &mut self.source,
                n: usize,
                d: usize,
                q: usize
            }
            self.max_query_count = q;
            Input { n, d, q }
        }

        pub fn output_query(&mut self, left_v: &Vec<usize>, right_v: &Vec<usize>) -> BalanceResult {
            if self.query_count >= self.max_query_count {
                // eprintln!("exceed query_count limit");
                return BalanceResult::Unknown;
            }
            self.query_count += 1;
            print!("{} {} ", left_v.len(), right_v.len());
            for e in left_v.iter() {
                print!("{} ", e);
            }
            for e in right_v.iter() {
                print!("{} ", e);
            }
            println!();
            self.flush();
            input! {
                from &mut self.source,
                s: String
            }
            match s.as_str() {
                "<" => BalanceResult::Left,
                ">" => BalanceResult::Right,
                "=" => BalanceResult::Equal,
                _ => panic!("failed to read_result: {}", s),
            }
        }

        pub fn output_d(&self, d: &Vec<usize>, for_debug: bool) {
            if for_debug {
                print!("#c ");
            }
            for e in d.iter() {
                print!("{} ", e);
            }
            println!();
            self.flush();
        }

        fn flush(&self) {
            std::io::stdout().flush().unwrap();
        }
    }
}
pub mod util {
    #![allow(unused)]

    use rustc_hash::{FxHashMap, FxHashSet};

    pub mod rnd {
        static mut S: usize = 88172645463325252;

        #[inline]
        pub fn next() -> usize {
            unsafe {
                S = S ^ S << 7;
                S = S ^ S >> 9;
                S
            }
        }

        #[inline]
        pub fn nextf() -> f64 {
            (next() & 4294967295) as f64 / 4294967296.
        }

        #[inline]
        pub fn gen_range(low: usize, high: usize) -> usize {
            assert!(low < high);
            (next() % (high - low)) + low
        }
    }

    pub mod time {
        static mut START: f64 = -1.;
        pub fn start_clock() {
            let _ = elapsed_seconds();
        }

        #[inline]
        pub fn elapsed_seconds() -> f64 {
            let t = std::time::SystemTime::now()
                .duration_since(std::time::UNIX_EPOCH)
                .unwrap()
                .as_secs_f64();
            unsafe {
                if START < 0. {
                    START = t;
                }
                t - START
            }
        }
    }

    #[derive(Default)]
    pub struct Queue {
        st_in: Vec<(u128, u16)>,
        st_out: Vec<(u128, u16)>,
    }

    impl Queue {
        pub fn push_back(&mut self, v: (u128, u16)) {
            self.st_in.push(v);
        }

        pub fn pop_front(&mut self) -> Option<(u128, u16)> {
            if self.st_out.is_empty() {
                if self.st_in.is_empty() {
                    return None;
                }
                while let Some(v) = self.st_in.pop() {
                    self.st_out.push(v);
                }
            }
            self.st_out.pop()
        }
    }

    pub type FastHashMap<K, V> = FxHashMap<K, V>;
    pub type FastHashSet<V> = FxHashSet<V>;
}

use crate::action::*;
use crate::def::*;
use crate::interactor::*;
use crate::util::*;

fn select_g_idx_pair(input: &Input) -> (usize, usize) {
    const P: f64 = 0.3;
    let par = 1
        + (time::elapsed_seconds() * (input.d as f64 / 3.).min(5.) / (TIME_LIMIT - 0.1)).round()
            as usize;
    let mut lighter_g_idx = 0;
    let mut heavier_g_idx = input.d - 1;
    for i in 0..par.min(input.d / 2) {
        if rnd::nextf() < P {
            lighter_g_idx = i;
            break;
        }
    }
    for i in ((input.d - input.d.min(par)).max(input.d / 2)..input.d).rev() {
        if rnd::nextf() < P {
            heavier_g_idx = i;
            break;
        }
    }
    (lighter_g_idx, heavier_g_idx)
}

fn solve(input: &Input, interactor: &mut Interactor) {
    const PAR: f64 = 1.0;
    let mut balancer = Balancer::new();

    // ランダムにグループに割り振る
    let mut groups = vec![vec![]; input.d];
    for i in 0..input.n {
        groups[i % input.d].push(i);
    }

    // ソートして順位をつける
    let mut rank = sort_groups(&groups, input, interactor, &mut balancer);
    eprintln!("after_sort: {} / {}", interactor.query_count, input.q);

    let mut trial_count = 0;
    let mut move_adopted_count = 0;
    let mut swap_adopted_count = 0;
    let mut swap2_adopted_count = 0;

    let action_p = [[0.5, 0.9, 1.0], [0.1, 0.2, 1.0]];

    while interactor.query_count < input.q && time::elapsed_seconds() < TIME_LIMIT - 0.1 {
        trial_count += 1;

        let stage = if time::elapsed_seconds() < PAR { 0 } else { 1 };

        let (lighter_g_idx, heavier_g_idx) = select_g_idx_pair(input);

        let p = rnd::nextf();
        let action = if p < action_p[stage][0] {
            action_move
        } else if p < action_p[stage][1] {
            action_swap
        } else {
            action_swap2
        };

        trial_count += 1;
        if action(
            heavier_g_idx,
            lighter_g_idx,
            &mut groups,
            &mut rank,
            input,
            &mut balancer,
            interactor,
        ) {
            if action == action_move {
                move_adopted_count += 1;
                eprintln!("[{} / {}] adopt move", interactor.query_count, input.q);
            } else if action == action_swap {
                swap_adopted_count += 1;
                eprintln!("[{} / {}] adopt swap", interactor.query_count, input.q);
            } else if action == action_swap2 {
                swap2_adopted_count += 1;
                eprintln!("[{} / {}] adopt swap2", interactor.query_count, input.q);
            }
        }

        let d = groups_to_output_d(&groups, input);
        interactor.output_d(&d, true);
    }

    if interactor.query_count < input.q {
        eprintln!("remaining query:     {}", input.q - interactor.query_count);
    }

    // 必要ないクエリを消化する
    while interactor.query_count < input.q {
        interactor.output_query(&vec![0], &vec![1]);
    }

    eprintln!("trial_count:         {trial_count}");
    eprintln!("move_adopted_count:  {move_adopted_count}");
    eprintln!("swap_adopted_count:  {swap_adopted_count}");
    eprintln!("swap2_adopted_count: {swap2_adopted_count}");

    let d = groups_to_output_d(&groups, input);
    interactor.output_d(&d, false);
}

fn main() {
    time::start_clock();

    let mut interactor = Interactor::new();
    let input = interactor.read_input();

    solve(&input, &mut interactor);
}

Submission Info

Judge Result