1. f가 maximum이 되기 위해선 가장 큰 비트부터 1로 만들어야 한다.

2. 그 비트가 1이 되기 위해선 모든 c에 대해서 또한 그 비트가 1이여야 한다.

3. c는 xor로 만들어지므로 a에서 그 비트가 0인 수들은 b에서 1과 매치, 1인 수들은 0과 매치 되야 한다.


그래서 i번째 비트를 기준으로 비교해서 3번 조건을 만족하면 a1(a에서 그 비트가 1인 수들의 모임)은 b0이랑만 b1은 a0이랑만 매칭될 수 있고

이제 i-1번째 비트를 기준으로 a11-b01, a10-b00, a01-b10, a00-b11 쌍이 전부 크기가 같으면 i-1번째도 1이 되고 아니면 i-2번째로 넘어가고...

이렇게 하면 모든 수들은 0<=i<=29에 대해서 i번째 비트를 검사할때마다 한번씩 총 30*2*10^5 = 600만번 검사해서 넉넉하게 통과하는거 아님??


Submission #169887924 - Codeforces


그런 생각으로 짜서 낸건데 진짜 왜 TLE인지 D번 30분 남기고 제출해서 드디어 4솔하나 했는데

30분동안 이게 왜 TLE 하다가 10연속 3솔이라 너무 화나서 잘수가없어