// O(N * log^2(N)) using binary search on a segment tree. // Let's see if we can distinghish it from the more efficient O(N * // log(N)), and refuse this O(N * log^2(N)) solution. #include #include #include #include using namespace std; // Segment tree implementation inspired from // https://codeforces.com/blog/entry/18051. void build_segment_tree(std::vector &tree, int N) { for (int i = N; i < 2 * N; ++i) tree[i] = 1; for (int i = N - 1; i > 0; --i) tree[i] = tree[i * 2] + tree[i * 2 + 1]; } // Sum on interval [left, right). int sum(std::vector &tree, int N, int left, int right) { int res = 0; for (left += N, right += N; left < right; left /= 2, right /= 2) { if (left % 2) res += tree[left++]; if (right % 2) res += tree[--right]; } return res; } // Sets value at position p. void modify(std::vector &tree, int N, int p, int value) { for (tree[p += N] = value; p > 1; p /= 2) tree[p / 2] = tree[p] + tree[p ^ 1]; } // Finds the smallest k such that the sum of the tree at indexes [0, // k] is equal to target_sum. int find_target_sum(std::vector &tree, int N, int target_sum) { int left = -1; int right = N; while (left + 1 < right) { int middle = (left + right) / 2; int s = sum(tree, N, 0, middle + 1); if (s >= target_sum) { right = middle; } else { left = middle; } } return right; } std::array, 2> pick_players(const std::array, 2> &choices) { std::array, 2> teams; int N = choices[0].size() * 2; std::vector tree(2 * N); build_segment_tree(tree, N); for (int i = 0; i < choices[0].size(); ++i) { for (int team = 0; team <= 1; team++) { int player = find_target_sum(tree, N, choices[team][i] + 1); modify(tree, N, player, 0); teams[team].push_back(player); } } return teams; } int main() { int N; std::cin >> N; assert(N % 2 == 0); std::array, 2> choices; choices[0].reserve(N); choices[1].reserve(N); for (int i = 0; i < N; ++i) { int choice; std::cin >> choice; // In the problem statement, the indexes are 1-based. choices[i >= N / 2].push_back(choice - 1); } auto teams = pick_players(choices); for (const auto &team : teams) { int i = 0; for (int player : team) { i++; // Players 0-based in the problem statement. std::cout << player + 1; if (i < N/2) { std::cout << " "; } else { std::cout << std::endl; } } } }