Submission #74712552

---

Source Code Expand

use proconio::input;
use itertools::Itertools;

struct Trie {
    ch: Vec<[usize; 2]>,
    cnt: Vec<usize>,
}

impl Trie {
    fn new() -> Self {
        Self { ch: vec![[0, 0]], cnt: vec![0] }
    }

    fn insert(&mut self, val: usize) {
        let mut u = 0;
        self.cnt[0] += 1;
        for i in (0..19).rev() {
            let b = (val >> i) & 1;
            if self.ch[u][b] == 0 {
                self.ch[u][b] = self.ch.len();
                self.ch.push([0, 0]);
                self.cnt.push(0);
            }
            u = self.ch[u][b];
            self.cnt[u] += 1;
        }
    }

    fn query_and_remove(&mut self, val: usize) -> usize {
        let mut u = 0;
        let mut p = 0;
        self.cnt[0] -= 1;
        for i in (0..19).rev() {
            let b = (val >> i) & 1;
            let preferred = b;
            let next;
            if self.ch[u][preferred] != 0 && self.cnt[self.ch[u][preferred]] > 0 {
                next = self.ch[u][preferred];
                p |= (preferred << i);
            } else {
                next = self.ch[u][1 - preferred];
                p |= ((1 - preferred) << i);
            }
            u = next;
            self.cnt[u] -= 1;
        }
        p
    }
}

fn main() {
    input! {
        T: usize,
    }
    for _ in 0..T {
        input! {
            N: usize,
        }

        let mut trie = Trie::new();
        for i in 1..=N {
            trie.insert(i);
        }

        let mut cur = 0;
        let mut ans = Vec::with_capacity(N);
        for _ in 0..N {
            let p = trie.query_and_remove(cur);
            ans.push(p);
            cur ^= p;
        }

        println!("{}", ans.into_iter().join(" "));
    }
}

Submission Info

Compile Error

warning: unnecessary parentheses around assigned value
  --> src/main.rs:39:22
   |
39 |                 p |= (preferred << i);
   |                      ^              ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
39 -                 p |= (preferred << i);
39 +                 p |= preferred << i;
   |

warning: unnecessary parentheses around assigned value
  --> src/main.rs:42:22
   |
42 |                 p |= ((1 - preferred) << i);
   |                      ^                    ^
   |
help: remove these parentheses
   |
42 -                 p |= ((1 - preferred) << i);
42 +                 p |= (1 - preferred) << i;
   |

warning: variable `T` should have a snake case name
  --> src/main.rs:53:9
   |
53 |         T: usize,
   |         ^ help: convert the identifier to snake case: `t`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `N` should have a snake case name
  --> src/main.rs:57:13
   |
57 |             N: usize,
   |             ^ help: convert the identifier to snake case: `n`

Judge Result