結果

問題 No.3591 I Love Graph
コンテスト
ユーザー urectanc
提出日時 2026-07-17 22:18:04
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
RE  
実行時間 -
コード長 1,749 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,403 ms
コンパイル使用メモリ 191,740 KB
実行使用メモリ 5,888 KB
平均クエリ数 3325.81
最終ジャッジ日時 2026-07-17 22:18:14
合計ジャッジ時間 9,502 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use itertools::Itertools;
use proconio::input;

fn main() {
    input! { n: usize }

    let ask = |a: &[usize], b: &[usize]| {
        assert!(!a.is_empty() && !b.is_empty());
        println!(
            "? {} {} {} {}",
            a.len(),
            b.len(),
            a.iter().map(|&i| i + 1).join(" "),
            b.iter().map(|&i| i + 1).join(" "),
        );
        input! { r: i8 }
        assert_ne!(r, -1);
        r == 1
    };

    let mut edges = vec![];

    let a = (0..n).collect_vec();
    let mut stack = vec![];
    for i in 0..n - 1 {
        let rest = &a[i + 1..];
        stack.push(rest);

        while let Some(vs) = stack.pop() {
            if edges.len() == 400 {
                break;
            }

            assert!(!vs.is_empty());
            if !ask(&[i], vs) {
                continue;
            }
            if vs.len() == 1 {
                edges.push((i, vs[0]));
                continue;
            }

            let (first, second) = vs.split_at(vs.len() / 2);
            if vs.len() == 2 {
                if ask(&[i], first) {
                    edges.push((i, first[0]));
                    stack.push(second);
                } else {
                    edges.push((i, second[0]));
                }
            } else if vs.len() == 3 {
                if ask(&[i], second) {
                    stack.push(first);
                    stack.push(second);
                } else {
                    edges.push((i, first[0]));
                }
            } else {
                stack.push(first);
                stack.push(second);
            }
        }
    }

    println!("! {}", edges.len());
    for &(u, v) in &edges {
        println!("{} {}", u + 1, v + 1);
    }
}
0