結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー ガルム
提出日時 2026-04-18 13:56:58
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 2,383 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 763 ms
コンパイル使用メモリ 192,744 KB
実行使用メモリ 30,332 KB
平均クエリ数 10.89
最終ジャッジ日時 2026-04-18 13:57:08
合計ジャッジ時間 7,980 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::io::{self, BufRead, Write};

fn ask<R: BufRead, W: Write>(input: &mut R, output: &mut W, a: usize, b: usize) -> i64 {
    writeln!(output, "? {} {}", a, b).unwrap();
    output.flush().unwrap();

    let mut line = String::new();
    input.read_line(&mut line).unwrap();
    let p = line.trim().parse::<i64>().unwrap();
    if p == -1 {
        std::process::exit(0);
    }
    p
}

fn answer<W: Write>(output: &mut W, s: &str) {
    writeln!(output, "! {}", s).unwrap();
    output.flush().unwrap();
}

fn unique_equal_digit(product: i64) -> Option<i64> {
    match product {
        1 => Some(1),
        25 => Some(5),
        49 => Some(7),
        64 => Some(8),
        81 => Some(9),
        _ => None,
    }
}

fn isqrt(x: i64) -> i64 {
    let mut r = (x as f64).sqrt() as i64;
    while (r + 1) * (r + 1) <= x {
        r += 1;
    }
    while r * r > x {
        r -= 1;
    }
    r
}

fn main() {
    let stdin = io::stdin();
    let mut input = stdin.lock();
    let stdout = io::stdout();
    let mut output = stdout.lock();

    let mut line = String::new();
    input.read_line(&mut line).unwrap();
    let n = line.trim().parse::<usize>().unwrap();

    let ms = n - 1;
    let mut digits = vec![0_i64; n];
    let mut products = vec![0_i64; n];
    let mut nonzero = Vec::new();

    for i in 0..ms {
        let p = ask(&mut input, &mut output, i, ms);
        products[i] = p;
        if p > 0 {
            nonzero.push(i);
        }
    }

    if nonzero.is_empty() {
        answer(&mut output, "-1");
        return;
    }

    if nonzero.len() == 1 {
        let i = nonzero[0];
        if let Some(d) = unique_equal_digit(products[i]) {
            digits[ms] = d;
            digits[i] = d;
            let x: String = digits.iter().rev().map(|&v| (b'0' + v as u8) as char).collect();
            answer(&mut output, &x);
        } else {
            answer(&mut output, "-1");
        }
        return;
    }

    let i = nonzero[0];
    let j = nonzero[1];
    let pair_product = ask(&mut input, &mut output, i, j);

    let ms_squared = products[i] * products[j] / pair_product;
    let ms_digit = isqrt(ms_squared);
    digits[ms] = ms_digit;

    for &idx in &nonzero {
        digits[idx] = products[idx] / ms_digit;
    }

    let x: String = digits.iter().rev().map(|&v| (b'0' + v as u8) as char).collect();
    answer(&mut output, &x);
}
0