結果

問題 No.1306 Exactly 2 Digits
ユーザー koba-e964koba-e964
提出日時 2020-12-06 23:57:17
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 130 ms / 2,000 ms
コード長 4,148 bytes
コンパイル時間 24,649 ms
コンパイル使用メモリ 384,736 KB
実行使用メモリ 25,476 KB
平均クエリ数 1237.29
最終ジャッジ日時 2024-07-17 09:57:06
合計ジャッジ時間 26,873 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
25,220 KB
testcase_01 AC 21 ms
24,836 KB
testcase_02 AC 22 ms
25,220 KB
testcase_03 AC 22 ms
24,836 KB
testcase_04 AC 21 ms
24,580 KB
testcase_05 AC 22 ms
24,580 KB
testcase_06 AC 24 ms
25,092 KB
testcase_07 AC 23 ms
24,580 KB
testcase_08 AC 24 ms
24,836 KB
testcase_09 AC 21 ms
24,580 KB
testcase_10 AC 23 ms
24,580 KB
testcase_11 AC 21 ms
25,220 KB
testcase_12 AC 22 ms
25,220 KB
testcase_13 AC 22 ms
25,220 KB
testcase_14 AC 22 ms
24,820 KB
testcase_15 AC 21 ms
24,964 KB
testcase_16 AC 22 ms
24,580 KB
testcase_17 AC 22 ms
25,220 KB
testcase_18 AC 21 ms
25,220 KB
testcase_19 AC 22 ms
24,580 KB
testcase_20 AC 22 ms
25,220 KB
testcase_21 AC 23 ms
24,580 KB
testcase_22 AC 22 ms
24,580 KB
testcase_23 AC 21 ms
25,220 KB
testcase_24 AC 23 ms
25,220 KB
testcase_25 AC 23 ms
24,836 KB
testcase_26 AC 22 ms
25,220 KB
testcase_27 AC 25 ms
24,836 KB
testcase_28 AC 22 ms
24,964 KB
testcase_29 AC 22 ms
24,580 KB
testcase_30 AC 22 ms
24,836 KB
testcase_31 AC 22 ms
24,964 KB
testcase_32 AC 22 ms
24,580 KB
testcase_33 AC 22 ms
24,836 KB
testcase_34 AC 22 ms
24,836 KB
testcase_35 AC 23 ms
25,220 KB
testcase_36 AC 23 ms
25,220 KB
testcase_37 AC 23 ms
24,836 KB
testcase_38 AC 22 ms
24,836 KB
testcase_39 AC 23 ms
25,220 KB
testcase_40 AC 23 ms
24,580 KB
testcase_41 AC 23 ms
24,836 KB
testcase_42 AC 22 ms
24,580 KB
testcase_43 AC 23 ms
25,220 KB
testcase_44 AC 24 ms
24,836 KB
testcase_45 AC 24 ms
24,836 KB
testcase_46 AC 24 ms
25,220 KB
testcase_47 AC 25 ms
25,092 KB
testcase_48 AC 26 ms
24,836 KB
testcase_49 AC 26 ms
24,836 KB
testcase_50 AC 28 ms
24,580 KB
testcase_51 AC 29 ms
24,836 KB
testcase_52 AC 30 ms
24,836 KB
testcase_53 AC 33 ms
24,836 KB
testcase_54 AC 31 ms
24,580 KB
testcase_55 AC 34 ms
25,076 KB
testcase_56 AC 36 ms
25,220 KB
testcase_57 AC 37 ms
25,208 KB
testcase_58 AC 38 ms
24,580 KB
testcase_59 AC 38 ms
25,204 KB
testcase_60 AC 45 ms
25,220 KB
testcase_61 AC 48 ms
24,580 KB
testcase_62 AC 49 ms
25,220 KB
testcase_63 AC 52 ms
25,220 KB
testcase_64 AC 49 ms
25,220 KB
testcase_65 AC 53 ms
25,220 KB
testcase_66 AC 59 ms
25,220 KB
testcase_67 AC 58 ms
25,220 KB
testcase_68 AC 60 ms
24,836 KB
testcase_69 AC 64 ms
25,220 KB
testcase_70 AC 63 ms
24,580 KB
testcase_71 AC 66 ms
24,836 KB
testcase_72 AC 66 ms
24,580 KB
testcase_73 AC 64 ms
25,220 KB
testcase_74 AC 76 ms
25,220 KB
testcase_75 AC 71 ms
24,580 KB
testcase_76 AC 82 ms
24,964 KB
testcase_77 AC 88 ms
25,476 KB
testcase_78 AC 92 ms
25,220 KB
testcase_79 AC 101 ms
24,580 KB
testcase_80 AC 105 ms
24,836 KB
testcase_81 AC 86 ms
25,220 KB
testcase_82 AC 107 ms
25,220 KB
testcase_83 AC 111 ms
24,580 KB
testcase_84 AC 116 ms
25,220 KB
testcase_85 AC 123 ms
24,836 KB
testcase_86 AC 105 ms
24,580 KB
testcase_87 AC 108 ms
25,220 KB
testcase_88 AC 130 ms
25,220 KB
testcase_89 AC 108 ms
24,836 KB
testcase_90 AC 98 ms
24,964 KB
testcase_91 AC 107 ms
24,836 KB
testcase_92 AC 98 ms
25,076 KB
testcase_93 AC 116 ms
25,220 KB
testcase_94 AC 100 ms
25,220 KB
testcase_95 AC 105 ms
24,836 KB
testcase_96 AC 95 ms
24,964 KB
testcase_97 AC 96 ms
24,836 KB
testcase_98 AC 92 ms
25,220 KB
testcase_99 AC 105 ms
24,580 KB
testcase_100 AC 106 ms
24,836 KB
testcase_101 AC 114 ms
24,820 KB
testcase_102 AC 96 ms
24,964 KB
testcase_103 AC 102 ms
25,220 KB
testcase_104 AC 102 ms
24,836 KB
testcase_105 AC 110 ms
24,580 KB
testcase_106 AC 94 ms
24,836 KB
testcase_107 AC 107 ms
24,964 KB
testcase_108 AC 98 ms
25,220 KB
testcase_109 AC 119 ms
24,836 KB
testcase_110 AC 96 ms
24,836 KB
testcase_111 AC 101 ms
24,580 KB
testcase_112 AC 91 ms
24,580 KB
testcase_113 AC 123 ms
25,476 KB
testcase_114 AC 123 ms
24,580 KB
testcase_115 AC 106 ms
24,580 KB
testcase_116 AC 127 ms
25,220 KB
testcase_117 AC 109 ms
25,476 KB
testcase_118 AC 119 ms
25,220 KB
testcase_119 AC 102 ms
24,836 KB
testcase_120 AC 93 ms
24,836 KB
testcase_121 AC 114 ms
24,836 KB
testcase_122 AC 110 ms
24,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;

#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}

fn get_word() -> String {
    let stdin = std::io::stdin();
    let mut stdin=stdin.lock();
    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.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

trait Int {
    fn ask(&self, a: usize, b: usize) -> (i64, i64) {
        println!("? {} {}", b + 1, a + 1);
        let a: i64 = get();
        let b: i64 = get();
        (a, b)
    }
    fn answer(&self, a: Vec<usize>) {
        print!("!");
        for a in a {
            print!(" {}", a);
        }
        println!();
    }
}

struct Wild;
impl Int for Wild {}

struct Local {
    n: usize,
    a: Vec<usize>,
}

impl Int for Local {
    fn ask(&self, a: usize, b: usize) -> (i64, i64) {
        let n = self.n;
        let x = self.a[a];
        let y = self.a[b];
        let mut v = vec![(y % n) as i64 - (x % n) as i64,
                         (y / n) as i64 - (x / n) as i64];
        v.sort();
        (v[0], v[1])
    }
    fn answer(&self, a: Vec<usize>) {
        assert_eq!(self.a, a);
    }
}

fn main() {
    let n: usize = get();
    let int = Wild;
    /*
    let mut a = vec![0; n * n - n];
    for i in 0..n * n - n {
        a[i] = n + i;
    }
    for i in 0..100 {
        let x = (5 * i + 3) % (n * n - n);
        let y = (7 * i + 1) % (n * n - n);
        a.swap(x, y);
    }
    let int = Local {
        n,
        a,
    };*/
    let mut res = vec![(0, 0); n * n - n];
    let mut hm = HashMap::new();
    hm.insert((0, 0), vec![0]);
    let mut freq = vec![0; 2 * n];
    freq[n] += 2;
    for i in 1..n * n - n {
        res[i] = int.ask(0, i);
        hm.entry(res[i]).or_insert(vec![]).push(i);
        let (x, y) = res[i];
        freq[(x + n as i64) as usize] += 1;
        freq[(y + n as i64) as usize] += 1;
    }
    let mut c = 0;
    let mut d = 0;
    for i in 0..2 * n {
        if freq[i] >= n {
            c = n + 1 - i;
            break;
        }
    }
    for i in 0..2 * n {
        if freq[i] % n > 0 {
            d = n - i;
            break;
        }
    }
    let mut truth = HashMap::new();
    for i in n..n * n {
        let dx = (i / n) as i64 - c as i64;
        let dy = (i % n) as i64 - d as i64;
        let (dx, dy) = if dx > dy {
            (dy, dx)
        } else {
            (dx, dy)
        };
        truth.entry((dx, dy)).or_insert(vec![]).push(i);
    }
    let mut ans = vec![0; n * n - n];
    let mut z = 0;
    let mut x = -(c as i64) + 1;
    let mut y = -(d as i64);
    if x > y {
        std::mem::swap(&mut x, &mut y);
    }
    for i in 0..n * n - n {
        if res[i] == (x, y) {
            z = i;
            break;
        }
    }
    let indices = hm[&(-(c as i64) + 1, (n - d - 1) as i64)].clone();
    assert!(indices.len() <= 2);
    let mut bl = indices[0];
    if indices.len() == 2 {
        if int.ask(z, indices[0]) != (0, n as i64 - 1) {
            bl = indices[1];
        }
    }
    for (k, v) in hm {
        assert_eq!(v.len(), truth[&k].len());
        if v.len() >= 2 {
            let (x, y) = int.ask(bl, v[0]);
            let val = (x + n as i64 - 1) as usize + (y + 1) as usize * n;
            if truth[&k][0] == val {
                for i in 0..2 {
                    ans[v[i]] = truth[&k][i];
                }
            } else {
                for i in 0..2 {
                    ans[v[i]] = truth[&k][1 - i];
                }
            }
        } else {
            ans[v[0]] = truth[&k][0];
        }
    }
    int.answer(ans);
}
0