******************************* *** The hack uses generator *** ******************************* ** Command line arguments ** no arguments ** Generated test ** 1 200000 200000 200000 28321 5137 52321 67825 62785 67057 10657 98545 107617 178609 65953 136369 71713 142321 194689 7441 158017 57457 108961 124369 11233 122065 77953 175729 7009 11089 148225 170257 143905 69745 152833 42481 181921 166993 147073 48817 39169 87889 186049 188689 41761 168337 54337 180913 180769 110737 72193 142609 178753 76273 176065 39409 125281 161233 95617 119473 183361 28657 182305 52177 138817 192817 152833 54385 194401 122449 81121 73777 15937 65617... ** Generator source ** #include #include #include #include #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); constexpr int n = 200'000; constexpr int m = 200'000; constexpr int q = 200'000; constexpr int size = 2048; constexpr int spacing = n / (2 * size); std::mt19937 rng(2285); // Interleave the two sides by label so unsuccessful lookups take varied paths. std::vector left(size), right(size); for (int i = 0; i < size; ++i) { left[i] = 1 + 2 * i * spacing; right[i] = left[i] + spacing; } // Each distinct shift gives another matching between the two sides. std::vector shifts(size); std::iota(shifts.begin(), shifts.end(), 0); std::shuffle(shifts.begin(), shifts.end(), rng); std::vector> edges; edges.reserve(m); for (int shift : shifts) { if (static_cast(edges.size()) == m) break; for (int i = 0; i < size && static_cast(edges.size()) < m; ++i) { edges.emplace_back(left[i], right[(i + shift) % size]); } } std::shuffle(edges.begin(), edges.end(), rng); std::cout << 1 << '\n' << n << ' ' << m << ' ' << q << '\n'; for (auto [u, v] : edges) { std::cout << u << ' ' << v << '\n'; } // Bit reversal spreads the keys of each intermediate component by label. std::vector reversed(size); for (int i = 1; i < size; ++i) { reversed[i] = reversed[i / 2] / 2 + (i % 2) * (size / 2); } int remaining = q; while (remaining > 0) { const int left_mask = rng() % size; const int right_mask = rng() % size; for (int width = 1; width < size && remaining > 0; width *= 2) { for (int side = 0; side < 2; ++side) { const auto& labels = side == 0 ? left : right; const int mask = side == 0 ? left_mask : right_mask; for (int i = 0; i < size && remaining > 0; i += 2 * width) { const int u = labels[reversed[i + width] ^ mask]; const int v = labels[reversed[i] ^ mask]; std::cout << u << ' ' << v << '\n'; --remaining; } } } // A cross-side merge explodes and restores all the singleton atoms. if (remaining > 0) { std::cout << left[left_mask] << ' ' << right[right_mask] << '\n'; --remaining; } } }