結果
問題 | No.1306 Exactly 2 Digits |
ユーザー |
![]() |
提出日時 | 2020-12-03 02:56:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 367 ms / 2,000 ms |
コード長 | 3,230 bytes |
コンパイル時間 | 17,807 ms |
コンパイル使用メモリ | 389,196 KB |
実行使用メモリ | 25,476 KB |
平均クエリ数 | 1236.78 |
最終ジャッジ日時 | 2024-07-17 08:22:59 |
合計ジャッジ時間 | 37,336 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 123 |
ソースコード
fn read() -> Vec<i32> {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();s.trim().split_whitespace().map(|s| s.parse().unwrap()).collect()}fn run() {let n = read()[0] as usize;let len = n * n - n;let mut cnt = 0;let mut query = |x: usize, y: usize| -> (i32, i32) {assert!(x != y);assert!(x < len);assert!(y < len);assert!(cnt < n * (n - 1) / 2 * 3);cnt += 1;println!("? {} {}", x + 1, y + 1);let a = read();(a[0], a[1])};let m = n as i32;let hash = |x: i32, y: i32| -> (i32, i32) {assert!(m <= x && x < m * m);assert!(m <= y && y < m * m);let mut p = x / m - y / m;let mut q = x % m - y % m;if p > q {std::mem::swap(&mut p, &mut q);}(p, q)};let mut memo = vec![(0, 0); len];let mut used = vec![];for i in 1..len {memo[i] = query(0, i);used.push((0, i, memo[i]));}let mut key = memo.clone();key.sort();let mut ans = vec![0; len];for i in m..(m * m) {let mut a = vec![];for j in m..(m * m) {a.push(hash(i, j));}a.sort();if a == key {assert!(ans[0] == 0);ans[0] = i;}}let mut map = std::collections::BTreeMap::new();for i in 1..len {map.entry(memo[i]).or_insert(vec![]).push(i);}for (&memo, index) in map.iter().filter(|p| p.1.len() == 1) {let i = index[0];for v in m..(m * m) {if v == ans[0] {continue;}if hash(ans[0], v) == memo {ans[i] = v;break;}}}for (&memo, index) in map.iter().filter(|p| p.1.len() == 2) {let (i, j) = (index[0], index[1]);let mut cond = vec![];for v in m..(m * m) {if v == ans[0] {continue;}if hash(ans[0], v) == memo {cond.push(v);}}assert!(cond.len() == 2);let (a, b) = hash(cond[0], cond[1]);if a.abs() != b.abs() {let p = query(i, j);used.push((i, j, p));let (x, y) = (cond[0], cond[1]);if p == hash(x, y) {ans[i] = x;ans[j] = y;} else {ans[i] = y;ans[j] = x;}} else {let q = ans.iter().position(|p| {*p > 0 && hash(*p, cond[0]) != hash(*p, cond[1])}).unwrap();let (x, y) = (cond[0], cond[1]);if hash(ans[q], cond[0]) == query(q, i) {ans[i] = x;ans[j] = y;} else {ans[i] = y;ans[j] = x;}}}{let mut p = ans.clone();p.sort();p.dedup();assert!(p.len() == len);assert!(p[0] == m);}print!("!");for a in ans {print!(" {}", a);}println!();}fn main() {run();}