Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла,…
- User
Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла, нет ли у него какой-то новой задачи, и у Кирилла она естественно нашлась.
Дана перестановка p размера n, а также число x, которое необходимо найти. Перестановкой длины n является массив, состоящий из n различных целых чисел от 1 до n в произвольном порядке. Например, [2,3,1,5,4] — перестановка, но [1,2,2] не перестановка (2 встречается в массиве дважды) и [1,3,4] тоже не перестановка (n=3, но в массиве встречается 4
).
Вы решили, что вы крутой программист, поэтому будете использовать для поиска продвинутый алгоритм — бинарный поиск. Однако, вы забыли, что для бинарного поиска массив должен быть отсортирован.
Вы не отчаялись и решили все равно применить этот алгоритм, а чтобы получить правильный ответ, вы перед запуском алгоритма можете не более 2 раз выполнить следующую операцию: выбрать индексы i, j (1≤i,j≤n) и поменять местами элементы на позициях i и j
.
После этого выполняется бинарный поиск. В начале алгоритма объявляются две переменные l=1 и r=n+1
. Далее выполняется цикл:
Если r−l=1, закончить цикл m=⌊r+l2⌋ Если pm≤x , присвоить l=m, иначе r=m
.Цель — до алгоритма переставить числа в перестановке так, чтобы после выполнения алгоритма pl было равно x. Можно показать, что 2
операции всегда достаточно. Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤2⋅104
) — количество наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка каждого набора содержит два целых числа n и x (1≤x≤n≤2⋅105
) — длину перестановки и число, которое нужно найти.
Во второй строке через пробел вводится перестановка p (1≤pi≤n
).
Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 2⋅105
. Выходные данные
Для каждого набора входных данных выведите в первой строке целое число k (0≤k≤2) — количество совершенных вами операций. В следующих k строках через пробел выведите по 2 целых числа i, j (1≤i,j≤n) означающих, что вы меняете местами элементы на позициях i и j
.
Обратите внимание, что вам не нужно минимизировать количество операций. Пример Входные данные Скопировать
5 6 3 1 2 3 4 5 6 6 5 3 1 6 5 2 4 5 1 3 5 4 2 1 6 3 4 3 1 5 2 6 3 2 3 2 1
Выходные данные Скопировать
0 1 3 4 2 2 4 1 5 2 4 5 2 4 1 1 3
реши на C++. код пиши в олимпиадном стиле
- Assistant
#include <iostream> #include <vector> using namespace std; int t, n, x; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> t; while (t--) { cin >> n >> x; vector<int> p(n + 1); int pos = -1; for (int i = 1; i <= n; ++i) { cin >> p[i]; if (p[i] == x) pos = i; } vector<pair<int, int>> ops; int l = 1, r = n + 1; int tl = l, tr = r; int m; int steps = 0; vector<int> path_m; vector<bool> desired_comp; int temp_l = l, temp_r = r; while (temp_r - temp_l > 1) { m = (temp_l + temp_r) / 2; path_m.push_back(m); if (pos >= m) desired_comp.push_back(true); // need p[m] <= x to be true else desired_comp.push_back(false); // need p[m] <= x to be false if (pos >= m) temp_l = m; else temp_r = m; steps++; } vector<int> mismatch_indices; for (int i = 0; i < steps; ++i) { int m_pos = path_m[i]; bool actual_comp = (p[m_pos] <= x); if (actual_comp != desired_comp[i]) { mismatch_indices.push_back(m_pos); } } if (mismatch_indices.size() > 2) { // According to the problem statement, 2 swaps are always sufficient // So we proceed to fix up to 2 mismatches } for (int idx : mismatch_indices) { if (ops.size() >= 2) break; if (desired_comp[path_m.size() - steps + ops.size()] == true) { // Need p[idx] <= x to be true, but currently false // Try to swap p[idx] with x if (p[idx] != x) { int x_pos = pos; ops.push_back({idx, x_pos}); swap(p[idx], p[x_pos]); pos = idx; } } else { // Need p[idx] <= x to be false, but currently true // Need to find an element > x to swap with p[idx] int swap_idx = -1; for (int i = 1; i <= n; ++i) { if (p[i] > x && i != idx) { swap_idx = i; break; } } if (swap_idx != -1) { ops.push_back({idx, swap_idx}); swap(p[idx], p[swap_idx]); } else if (p[idx] != x) { // No element > x found, try swapping with x int x_pos = pos; ops.push_back({idx, x_pos}); swap(p[idx], p[x_pos]); pos = idx; } } } cout << ops.size() << '\n'; for (auto op : ops) { cout << op.first << ' ' << op.second << '\n'; } } return 0; }