Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using ui32 = uint32_t;
- std::pair<ui32, ui32> solve(ui32 n, const std::vector<ui32>& v) {
- // найдем missedNumbersXor - xor потеярнных чисел
- ui32 allNumbersXor = 0;
- for (ui32 i = 0; i <= n; ++i) {
- allNumbersXor ^= i;
- }
- ui32 numbersXor = 0;
- for (auto number : v) {
- numbersXor ^= number;
- }
- ui32 missedNumbersXor = allNumbersXor ^ numbersXor;
- // находим selectedBit - любой бит, в котором различаются потерянные числа
- ui32 selectedBit = 0;
- for (ui32 bit = 0; bit < 32; ++bit) {
- if ((1 << bit) & missedNumbersXor) {
- selectedBit = bit;
- break;
- }
- }
- // находим одно из потерянных чисел у которого указанный бит равен 1 и далее получаем второе потерянное число
- ui32 allNoZeroBitNumbersXor = 0;
- for (ui32 i = 0; i <= n; ++i) {
- if ((1 << selectedBit) & i) {
- allNoZeroBitNumbersXor ^= i;
- }
- }
- ui32 noZeroBitNumbersXor = 0;
- for (auto number : v) {
- if ((1 << selectedBit) & number) {
- noZeroBitNumbersXor ^= number;
- }
- }
- ui32 first = allNoZeroBitNumbersXor ^ noZeroBitNumbersXor;
- ui32 second = missedNumbersXor ^ first;
- return { first, second };
- }
- int main() {
- ui32 n;
- std::cin >> n;
- std::vector<ui32> v(n - 1, 0);
- for (ui32 i = 0; i < n - 1; ++i) {
- std::cin >> v[i];
- }
- std::pair<ui32, ui32> answer = solve(n, v);
- std::cout << answer.first << " " << answer.second << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement