結果

問題 No.3798 algo to goal
ユーザー urectanc
提出日時 2026-11-13 23:44:52
言語 Rust
(1.99.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WA  
実行時間 -
コード長 2,382 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,726 ms
コンパイル使用メモリ 190,708 KB
実行使用メモリ 23,552 KB
最終ジャッジ日時 2026-11-13 23:45:23
合計ジャッジ時間 8,651 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use itertools::Itertools;
use proconio::{fastout, input, marker::Chars};

#[fastout]
fn main() {
    input! { t: usize }

    for _ in 0..t {
        let ans = solve();
        println!("{}", if ans { "Yes" } else { "No" });
    }
}

fn solve() -> bool {
    input! {
        s: Chars,
        t: Chars,
    }
    let n = s.len();

    let f = |s: &[char]| {
        let even = s.iter().copied().step_by(2).collect_vec();
        let odd = s.iter().copied().skip(1).step_by(2).collect_vec();
        (even, odd)
    };

    let (mut se, mut so) = f(&s);
    let (mut te, mut to) = f(&t);
    se.sort_unstable();
    so.sort_unstable();
    te.sort_unstable();
    to.sort_unstable();

    if se != te || so != to {
        return false;
    }

    {
        let mut s = s.clone();
        s.sort_unstable();
        s.dedup();
        if s.len() < n {
            return true;
        }
    }

    assert!(n <= 26);

    let x = inv(&s);
    let y = inv(&t);
    x % 2 == y % 2
}

fn inv(a: &[char]) -> usize {
    let n = a.len();
    let mut res = 0;
    for j in 0..n {
        for i in 0..j {
            if a[i] > a[j] {
                res += 1;
            }
        }
    }
    res
}

#[allow(unused)]
fn experiment() {
    use std::collections::BTreeSet;

    fn inv(a: &[usize]) -> usize {
        let n = a.len();
        let mut res = 0;
        for j in 0..n {
            for i in 0..j {
                if a[i] > a[j] {
                    res += 1;
                }
            }
        }
        res
    }

    let n = 4;
    let mut seen = BTreeSet::new();
    let mut init = (0..n).collect_vec();
    init.extend_from_within(..);

    let n = init.len();
    seen.insert(init.clone());
    let mut stack = vec![init.clone()];
    while let Some(state) = stack.pop() {
        println!("o {state:?} {}", inv(&state));
        for i in 0..=n - 4 {
            let mut nstate = state.clone();
            nstate.swap(i, i + 2);
            nstate.swap(i + 1, i + 3);
            if seen.insert(nstate.clone()) {
                stack.push(nstate);
            }
        }
    }

    for v in init.iter().copied().permutations(n) {
        if (0..n).any(|i| v[i] % 2 != i % 2) || seen.contains(&v) {
            continue;
        }
        eprintln!("x {v:?} {}", inv(&v));
    }
}

// 偶奇は不変
// 転倒数の偶奇
// distinctでなければなんでもOK
0