結果
| 問題 | No.1306 Exactly 2 Digits |
| ユーザー |
 koba-e964
|
| 提出日時 | 2020-12-06 23:44:45 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,457 bytes |
| コンパイル時間 | 16,298 ms |
| コンパイル使用メモリ | 383,660 KB |
| 実行使用メモリ | 25,604 KB |
| 平均クエリ数 | 1237.20 |
| 最終ジャッジ日時 | 2024-07-17 10:00:01 |
| 合計ジャッジ時間 | 43,996 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | WA | - |
| testcase_64 | WA | - |
| testcase_65 | WA | - |
| testcase_66 | WA | - |
| testcase_67 | WA | - |
| testcase_68 | WA | - |
| testcase_69 | WA | - |
| testcase_70 | WA | - |
| testcase_71 | WA | - |
| testcase_72 | WA | - |
| testcase_73 | WA | - |
| testcase_74 | WA | - |
| testcase_75 | WA | - |
| testcase_76 | WA | - |
| testcase_77 | WA | - |
| testcase_78 | WA | - |
| testcase_79 | WA | - |
| testcase_80 | WA | - |
| testcase_81 | WA | - |
| testcase_82 | WA | - |
| testcase_83 | WA | - |
| testcase_84 | WA | - |
| testcase_85 | WA | - |
| testcase_86 | WA | - |
| testcase_87 | WA | - |
| testcase_88 | WA | - |
| testcase_89 | WA | - |
| testcase_90 | WA | - |
| testcase_91 | WA | - |
| testcase_92 | WA | - |
| testcase_93 | WA | - |
| testcase_94 | WA | - |
| testcase_95 | WA | - |
| testcase_96 | WA | - |
| testcase_97 | WA | - |
| testcase_98 | WA | - |
| testcase_99 | WA | - |
| testcase_100 | WA | - |
| testcase_101 | WA | - |
| testcase_102 | WA | - |
| testcase_103 | WA | - |
| testcase_104 | WA | - |
| testcase_105 | WA | - |
| testcase_106 | WA | - |
| testcase_107 | WA | - |
| testcase_108 | WA | - |
| testcase_109 | WA | - |
| testcase_110 | WA | - |
| testcase_111 | WA | - |
| testcase_112 | WA | - |
| testcase_113 | WA | - |
| testcase_114 | WA | - |
| testcase_115 | WA | - |
| testcase_116 | WA | - |
| testcase_117 | WA | - |
| testcase_118 | WA | - |
| testcase_119 | WA | - |
| testcase_120 | WA | - |
| testcase_121 | WA | - |
| testcase_122 | WA | - |
ソースコード
#[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!("? {} {}", a + 1, b + 1);
let a: i64 = get();
let b: i64 = get();
(a, b)
}
fn answer(&self, a: Vec<usize>) {
print!("!");
for a in a {
print!(" {}", a);
}
}
}
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 solve() {
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;
}
}
eprintln!("c, d = {}, {}", c, d);
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);
eprintln!("indices = {:?}", indices);
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);
}
fn main() {
// In order to avoid potential stack overflow, spawn a new thread.
let stack_size = 104_857_600; // 100 MB
let thd = std::thread::Builder::new().stack_size(stack_size);
thd.spawn(|| solve()).unwrap().join().unwrap();
}