# [Platinum I] 杞人憂天 [문제 링크](https://www.acmicpc.net/problem/34244) ## 문제 설명 <p><strong>이 문제는 투 스텝 문제입니다.</strong></p> <p>A는 B에게 메시지를 보내고 싶다. 메시지는 정수 $X$로 나타낼 수 있지만 그냥 보내면 누군가 그 내용을 감청할지도 모른다. 그래서 주변에 있던 $N$개의 카드를 이용해 메시지를 감추기로 했다. 각 카드의 앞면과 뒷면에는 $1$ 이상 $2N$ 이하의 정수가 $1$개씩 적혀 있으며 카드들에 적혀 있는 $2N$개의 수는 모두 다르다.</p> <p>A는 카드마다 앞면과 뒷면의 수 중 하나를 선택하여, 순서를 섞어 B에게 전송한다. B는 A와 사전에 전략을 상의할 순 있지만 각 카드에 어떤 수가 적혀 있었는지는 알 수 없다. B는 $X$의 값을 알아맞혀야 한다.</p> <p>A와 B의 전략을 구현해보자.</p> ## 입력 <p>당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스코드에 두 가지 실행 과정을 모두 구현해야 한다.</p> <p>첫째 줄에 입력의 종류를 나타내는 정수 $T$가 주어진다. ($T \in \left\{1,2\right\}$)</p> <p>$T=1$인 경우 A의 역할을 수행하고 $T=2$인 경우 B의 역할을 수행해야 한다.</p> ## 첫번째 단계 <p>둘째 줄에 카드의 총 개수와 보낼 메시지를 나타내는 두 정수 $N$, $X$가 공백으로 구분되어 주어진다. ($N=100, 1\leq X \leq 10^{18}$)</p> <p>셋째 줄부터 $N$줄에 걸쳐 카드에 대한 정보가 주어진다. $i+2$번째 줄에 $i$번째 카드의 앞면과 뒷면에 적혀있는 두 정수 $a_i$, $b_i$가 공백으로 구분되어 주어진다. $N$개의 카드에 적힌 모든 수는 서로 다르다. ($1 \leq a_i,b_i \leq 2N$)</p> <p>당신은 B에게 보낼 $N$개의 정수 $x_1, x_2, \cdots, x_{N}$을 공백으로 구분해 출력해야 한다. $x_i$는 $i$번째 카드에서 고른 수를 나타낸다. ($x_i \in \left\{a_i, b_i\right\}$)</p> ## 두번째 단계 <p>둘째 줄에 카드의 총 개수를 나타내는 정수 $N$이 공백으로 구분되어 주어진다. ($N=100$)</p> <p>셋째 줄에 A가 고른 $N$개의 수 $x_1, x_2, \cdots, x_{N}$이 공백으로 구분되어 주어진다. 단, 수들의 순서는 오름차순으로 정렬되어 주어진다. ($1\leq x_i \leq 2N$)</p> <p>당신은 A가 보내고자 한 메시지를 나타내는 정수 $X$를 출력해야 한다. ($1\leq X \leq 10^{18}$)</p> ## 풀이 2N개의 숫자에 대해 1~2^60 범위의 랜덤한 수를 할당한다. 처음엔 카드의 앞면이나 뒷면이나 아무거나 선택하고, 선택된 면에 할당된 숫자들의 xor값이 x가 되도록 이진 가우스 소거법으로 적당히 뒤집어서 해결할 수 있다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; bitset<100> reversed[60]; ull w[201], basis[60], idx[60]; int main() { ios::sync_with_stdio(0); cin.tie(0); // 랜덤한 가중치 할당 mt19937_64 rd(123456789); uniform_int_distribution<ull> rnd(0, (1ULL<<60)-1); for(int i=1;i<=200;i++) w[i] = rnd(rd); int t; cin >> t; if(t==1) { ull n, x; cin >> n >> x; // 처음에는 아무거나 선택 ull xorVal = x; vector<pair<int, int>> v; for(int i=0;i<n;i++) { int a, b; cin >> a >> b; v.push_back({a, b}); xorVal ^= w[a]; } // xor해서 x가 나오도록 가우스 소거법으로 적당히 카드 뒤집기 for(int i=0;i<n;i++) { ull cur = w[v[i].first]^w[v[i].second]; bitset<100> curReversed; curReversed[i]=1; for(int j=59;j>=0;j--) { if(((cur>>j)&1ULL)==0) continue; if(!basis[j]) { basis[j] = cur; idx[j] = i; reversed[j] = curReversed; break; } cur ^= basis[j]; curReversed ^= reversed[j]; } } ull cur=xorVal; bitset<100> curReversed; for(int i=59;i>=0;i--) { if(((cur>>i)&1ULL)==0) continue; cur ^= basis[i]; curReversed ^= reversed[i]; } for(int i=0;i<n;i++) cout << (curReversed[i] ? v[i].second : v[i].first) << ' '; } else { int n; cin >> n; ull ret=0; while(n--) { int x; cin >> x; ret ^= w[x]; } cout << ret; } } ```