Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла,…

  1. 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++. код пиши в олимпиадном стиле

  2. 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;
    }