結果

問題 No.3622 Perfect Matching of Crab
コンテスト
ユーザー urectanc
提出日時 2026-08-14 21:41:54
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 77 ms / 2,000 ms
+ 486µs
コード長 932 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,985 ms
コンパイル使用メモリ 206,224 KB
実行使用メモリ 12,548 KB
最終ジャッジ日時 2026-08-14 21:42:10
合計ジャッジ時間 7,649 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::HashMap;

use proconio::{fastout, input, marker::Usize1};

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

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

fn solve() -> bool {
    input! {
        n: usize,
        xyc: [(Usize1, Usize1, char); 2* n],
    }

    let mut count = [0usize; 2];

    let mut row = HashMap::new();
    let mut col = HashMap::new();
    for &(x, y, c) in &xyc {
        count[(c == 'y') as usize] += 1;
        if c == 'x' {
            *row.entry(y).or_insert(0) += 1;
        } else {
            *col.entry(x).or_insert(0) += 1;
        }
    }

    let d = count[0].abs_diff(count[1]);
    if d == 0 {
        return true;
    }

    let pair = if count[0] > count[1] {
        row.values().map(|&x| x / 2).sum::<usize>()
    } else {
        col.values().map(|&x| x / 2).sum::<usize>()
    };
    2 * pair >= d
}
0