#589987 (Rust) No.1306 Exactly 2 Digits

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	koba-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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#[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);
}

yukicoder

結果

テストケース

ソースコード