結果

問題 No.594 壊れた宝物発見機
ユーザー phsplsphspls
提出日時 2020-07-01 23:06:22
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 433 ms / 2,000 ms
コード長 4,434 bytes
コンパイル時間 12,167 ms
コンパイル使用メモリ 402,392 KB
実行使用メモリ 448,480 KB
平均クエリ数 179.65
最終ジャッジ日時 2024-07-17 03:54:31
合計ジャッジ時間 22,801 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 425 ms
448,352 KB
testcase_01 AC 424 ms
448,096 KB
testcase_02 AC 423 ms
448,352 KB
testcase_03 AC 424 ms
448,224 KB
testcase_04 AC 433 ms
447,960 KB
testcase_05 AC 424 ms
447,968 KB
testcase_06 AC 426 ms
448,480 KB
testcase_07 AC 428 ms
447,704 KB
testcase_08 AC 421 ms
448,096 KB
testcase_09 AC 423 ms
447,960 KB
testcase_10 AC 422 ms
448,216 KB
testcase_11 AC 424 ms
448,088 KB
testcase_12 AC 420 ms
447,968 KB
testcase_13 AC 418 ms
447,712 KB
testcase_14 AC 423 ms
447,960 KB
testcase_15 AC 424 ms
448,224 KB
testcase_16 AC 427 ms
448,344 KB
testcase_17 AC 424 ms
448,240 KB
testcase_18 AC 420 ms
447,712 KB
testcase_19 AC 425 ms
448,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn update(xyz: (usize, usize, usize), xyzd: &mut Vec<Vec<Vec<Option<usize>>>>) {
    let x = xyz.0;
    let y = xyz.1;
    let z = xyz.2;
    if xyzd[x][y][z].is_some() { return; }
    println!("? {} {} {}", x as isize - 150, y as isize - 150, z as isize - 150);
    let mut d = String::new();
    std::io::stdin().read_line(&mut d).ok();
    let d: usize = d.trim().parse().unwrap();
    xyzd[x][y][z] = Some(d);
}

fn get_coord(axis: usize, base: usize, a: usize, b: usize) -> (usize, usize, usize) {
    match axis {
        0 => (base, a, b),
        1 => (b, base, a),
        _ => (a, b, base)
    }
}

fn get_min_idx(points: &Vec<usize>, axis: usize, a: usize, b: usize, xyzd: &Vec<Vec<Vec<Option<usize>>>>) -> usize {
    let i0 = get_coord(axis, points[0], a, b);
    let i1 = get_coord(axis, points[1], a, b);
    let i2 = get_coord(axis, points[2], a, b);
    let i3 = get_coord(axis, points[3], a, b);
    if    xyzd[i0.0][i0.1][i0.2].unwrap() == xyzd[i1.0][i1.1][i1.2].unwrap()
       && xyzd[i0.0][i0.1][i0.2].unwrap() == xyzd[i2.0][i2.1][i2.2].unwrap()
       && xyzd[i0.0][i0.1][i0.2].unwrap() == xyzd[i3.0][i3.1][i3.2].unwrap()
    { return 4; }
    let temp = vec![
        (i0, xyzd[i0.0][i0.1][i0.2].unwrap())
      , (i1, xyzd[i1.0][i1.1][i1.2].unwrap())
      , (i2, xyzd[i2.0][i2.1][i2.2].unwrap())
      , (i3, xyzd[i3.0][i3.1][i3.2].unwrap())
    ];
    let temp = temp.iter().min_by_key(|pair| pair.1).unwrap().0;
    if temp == i0 { return 0; }
    else if temp == i1 { return 1; }
    else if temp == i2 { return 2; }
    else { return 3; }
}

fn fuzzy_detect(axis: usize, low_up: &mut Vec<Vec<usize>>, xyzd: &mut Vec<Vec<Vec<Option<usize>>>>) {
    let mut lower = low_up[axis][0];
    let mut upper = low_up[axis][1];
    let a = match axis {
        0 => (low_up[1][0] + low_up[1][1]) / 2,
        1 => (low_up[2][0] + low_up[2][1]) / 2,
        _ => (low_up[0][0] + low_up[0][1]) / 2
    };
    let b = match axis {
        0 => (low_up[2][0] + low_up[2][1]) / 2,
        1 => (low_up[0][0] + low_up[0][1]) / 2,
        _ => (low_up[1][0] + low_up[1][1]) / 2
    };
    update(get_coord(axis, lower, a, b), xyzd);
    update(get_coord(axis, upper, a, b), xyzd);
    while upper - lower > 4 {
        let lmiddle: usize = (lower * 2 + upper) / 3;
        let rmiddle: usize = (lower + upper * 2) / 3;
        update(get_coord(axis, lmiddle, a, b), xyzd);
        update(get_coord(axis, rmiddle, a, b), xyzd);
        let min_idx = get_min_idx(&vec![lower, lmiddle, rmiddle, upper], axis, a, b, xyzd);
        match min_idx {
            0 => { upper = lmiddle; match axis { 0 => {low_up[0][1] = lmiddle;}, 1 => {low_up[1][1] = lmiddle;}, _ => {low_up[2][1] = lmiddle;}}; },
            1 => { upper = rmiddle; match axis { 0 => {low_up[0][1] = rmiddle;}, 1 => {low_up[1][1] = rmiddle;}, _ => {low_up[2][1] = rmiddle;}}; },
            2 => { lower = lmiddle; match axis { 0 => {low_up[0][0] = lmiddle;}, 1 => {low_up[1][0] = lmiddle;}, _ => {low_up[2][0] = lmiddle;}}; },
            3 => { lower = rmiddle; match axis { 0 => {low_up[0][0] = rmiddle;}, 1 => {low_up[1][0] = rmiddle;}, _ => {low_up[2][0] = rmiddle;}}; },
            _ => { break; }
        }
    }
}

fn main() {
    let mut xyzd: Vec<Vec<Vec<Option<usize>>>> = vec![vec![vec![None; 301]; 301]; 301];
    //x, y, z
    let mut low_up: Vec<Vec<usize>> = vec![vec![0, 300]; 3];
    let mut prev = low_up.clone();
    loop {
        fuzzy_detect(0, &mut low_up, &mut xyzd);
        fuzzy_detect(1, &mut low_up, &mut xyzd);
        fuzzy_detect(2, &mut low_up, &mut xyzd);
        if prev.iter().zip(low_up.iter()).filter(|pair| pair.0[0] == pair.1[0] && pair.0[1] == pair.1[1]).count() == 3 {
            break;
        }
        prev = low_up.clone();
    }
    let mut result: Option<(usize, usize, usize, usize)> = None;
    for x in low_up[0][0]..=low_up[0][1] {
        for y in low_up[1][0]..=low_up[1][1] {
            for z in low_up[2][0]..=low_up[2][1] {
                update((x, y, z), &mut xyzd);
                if result.is_none() {
                    result = Some((x, y, z, xyzd[x][y][z].unwrap()));
                } else if result.unwrap().3 > xyzd[x][y][z].unwrap() {
                    result = Some((x, y, z, xyzd[x][y][z].unwrap()));
                }
            }
        }
    }
    println!("! {} {} {}", result.unwrap().0 as isize - 150, result.unwrap().1 as isize - 150, result.unwrap().2 as isize - 150);
}
0