結果

問題 No.282 おもりと天秤(2)
ユーザー koba-e964koba-e964
提出日時 2016-03-22 03:26:10
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 177 ms / 5,000 ms
コード長 3,022 bytes
コンパイル時間 12,734 ms
コンパイル使用メモリ 403,916 KB
実行使用メモリ 25,556 KB
平均クエリ数 30.58
最終ジャッジ日時 2024-07-16 23:06:58
合計ジャッジ時間 16,758 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
25,232 KB
testcase_01 AC 27 ms
24,592 KB
testcase_02 AC 25 ms
24,848 KB
testcase_03 AC 25 ms
24,976 KB
testcase_04 AC 25 ms
25,232 KB
testcase_05 AC 25 ms
25,232 KB
testcase_06 AC 26 ms
25,232 KB
testcase_07 AC 24 ms
24,848 KB
testcase_08 AC 26 ms
24,976 KB
testcase_09 AC 24 ms
25,124 KB
testcase_10 AC 76 ms
24,848 KB
testcase_11 AC 165 ms
24,976 KB
testcase_12 AC 96 ms
24,848 KB
testcase_13 AC 116 ms
24,592 KB
testcase_14 AC 152 ms
24,848 KB
testcase_15 AC 173 ms
25,232 KB
testcase_16 AC 33 ms
25,232 KB
testcase_17 AC 117 ms
25,232 KB
testcase_18 AC 138 ms
24,848 KB
testcase_19 AC 146 ms
25,232 KB
testcase_20 AC 177 ms
24,836 KB
testcase_21 AC 176 ms
24,836 KB
testcase_22 AC 173 ms
24,836 KB
testcase_23 AC 23 ms
25,556 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    return ret;
}
#[allow(dead_code)]
fn getword() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.is_err() ||u8b[0] <= ' ' as u8 {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = std::string::String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}
#[allow(dead_code)]
fn parse<T : std::str::FromStr>(s : &str) -> T {
     return s.parse::<T>().ok().unwrap();
}

fn query(n: usize, ary: &mut [Option<usize>], que: &[(usize, usize)]) {
    let mut output = vec![0; 2 * n];
    let mut numq = 0;
    for i in 0 .. n {
        if i < que.len() {
            let (x, y) = que[i];
            if let (Some(u), Some(v)) = (ary[x], ary[y]) {
                output[2 * i] = u;
                output[2 * i + 1] = v;
                numq += 1;
            }
        }
    }
    if numq == 0 { // no question
        return;
    }
    print!("?");
    for o in output.iter() {
        print!(" {}", o);
    }
    println!("");
    let mut ans = vec!['@'; n];
    for i in 0 .. n {
        ans[i] = getword().chars().nth(0).unwrap();
        if i < n && ans[i] == '>' {
            let (x, y) = que[i];
            //swap
            if let (Some(_), Some(_)) = (ary[x], ary[y]) {
                let tmp = ary[x];
                ary[x] = ary[y];
                ary[y] = tmp;
            }
        }
    }
    
}

fn bitonic_sort(n: usize, exp: usize, ary: &mut [Option<usize>]) {
    assert!(ary.len() == (1 << exp));
    for i in 0 .. exp {
        let s = 1 << i;
        let t = 1 << (exp - 1 - i);
        let mut que = Vec::new();
        for k in 0 .. t {
            for p in 0 .. s {
                que.push((p + 2 * s * k, 2 * s - 1 - p + 2 * s * k));
            }
        }
        query(n, ary, &que);
        for j in (0 .. i).rev() {
            que.clear();
            let s = 1 << j;
            let t = 1 << (exp - 1 - j);
            for k in 0 .. t {
                for p in 0 .. s {
                    que.push((p + 2 * s * k, p + s + 2 * s * k)); 
                }
            }
            query(n, ary, &que);
        }
    }
}

fn main() {
    let n: usize = parse(&getword());
    let mut exp = 1;
    while n > (1 << exp) { // find the least exp s.t. n <= 2^exp.
        exp += 1;
    }
    let mut ary = vec![Some(1usize);1 << exp];
    for i in 0 .. 1 << exp {
        ary[i] = if i < n { Some(i + 1) } else { None };
    }
    bitonic_sort(n, exp, &mut ary); // perform bitonic sort on a 2^exp-elem array.
    print!("!");
    for i in 0 .. n {
        print!(" {}", ary[i].unwrap());
    }
    println!("");
}
0