log 2021-09-06

---

• sport
  • cf 1567 복습
    • B

sport

cf 1567 복습

B

https://codeforces.com/contest/1567/problem/B

hint

MEX도 XOR도 이해는 했는데, 접근 방법이 막막해서 못풀었다. 알고보니, 배열의 원소는 중복되어도 되는 것이었다. 그래서 MEX 조건만 맞춘 다음, XOR을 그리디하게 맞추면 되는 것이었다.

그렇다 해도, 설마 비트 계산조차 없이 풀 수 있는 문제일 줄은 몰랐다. 의외로 xor문제가 항상 복잡한 비트 계산이 필요한 게 아니라, 생각만 잘 하면 그냥 풀 수 있는 듯하다.

또한, 테케가 50만, 입력이 30만씩이므로 O(tn)으로 풀면 틀린다. 그래서 xor들을 미리 계산해 두어야 한다.

rust solution

    fn solve<R: io::BufRead, W: io::Write>(scan: &mut UnsafeScanner<R>, out: &mut W) {
        let cases = ri32(scan);

        let mut xors = vec![0];
        for i in 0..300001 {
            xors.push(xors[i as usize] ^ i);
        }

        for case in 0..cases {
            let (mex, xor) = (ru32(scan), ru32(scan));
            
            // get the xor of all the elements
            let mut xor_arr: u32 = xors[mex as usize];

            // check if xor_arr is xor
            let mut ans = 0;
            if xor_arr == xor {
                // writeln!(out, "Case #{}: type 1 {}", case, mex).unwrap();
                ans = mex;
            } else {
                // if not, then we need to add a number to the array to make it xor
                let b = xor_arr ^ xor;
                if b == mex {
                    // writeln!(out, "Case #{}: type 2 {}", case, mex+2).unwrap();
                    ans = mex+2;
                } else {
                    // writeln!(out, "Case #{}: type 3 {}", case, mex+1).unwrap();
                    ans = mex+1;
                }
            }

            writeln!(out, "{}", ans);
        }
    }

---