исправь следующий код: #define GLIBCXXDEBUG #include <bits/stdc++.h> #define tc int t;…
- User
исправь следующий код: #define _GLIBCXX_DEBUG #include <bits/stdc++.h> #define tc int t; cin >> t; while(t--) #define sz(x) int((x).size()) typedef long long ll; using namespace std; int sim(const vector &a,int x) { int l=1;int r=sz(a); while(r-l>1){ int mid=(l+r)/2; if(a[mid]<=x){ l=mid; } else{ r=mid; } } return l; } void solve() { int n;cin>>n; int x;cin>>x; vectorp(n); for(int i=0;i<n;i++){ cin>>p[i]; } int l1=sim(p,x); vector<pair<int,int>>ops; long long pos=find(p.begin(),p.end(),x)-p.begin(); if(l1<n&&p[l1]==x){cout<<0;}else{ ops.emplace_back(l1,pos); swap(p[l1],p[pos]); int l2=sim(p,x); if(l2<n&&p[l2]!=x){ int pos1=find(p.begin(),p.end(),x)-p.begin(); if(pos1!=l1){ ops.emplace_back(l2,pos1); swap(p[l2],p[pos1]); } } } cout<<ops.size()<<"\n"; for(auto &[i,j]:ops){ cout<<i+1<<" "<<j+1<<"\n"; } }
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); tc{ solve(); }; return 0; }
для следующей задачи: Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла, нет ли у него какой-то новой задачи, и у Кирилла она естественно нашлась.
Дана перестановка 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
- Assistant
Извините за возможную путаницу в коде, давайте исправим его, чтобы он правильно решал задачу. Проблема в том, что исходный код использует смешение индексирования с 0 и с 1, что приводит к ошибкам при доступе к элементам массива.
Вот исправленный код:
#define _GLIBCXX_DEBUG #include <bits/stdc++.h> #define tc int t; cin >> t; while(t--) #define sz(x) int((x).size()) typedef long long ll; using namespace std; int sim(const vector<int> &a, int x) { int l = 0, r = sz(a); while (r - l > 1) { int mid = (l + r) / 2; if (a[mid] <= x) l = mid; else r = mid; } return l; } void solve() { int n; cin >> n; int x; cin >> x; vector<int> p(n); for (int i = 0; i < n; i++){ cin >> p[i]; } int l1 = sim(p, x); vector<pair<int, int>> ops; int pos = find(p.begin(), p.end(), x) - p.begin(); if (p[l1] == x){ cout << 0 << "\n"; } else { ops.emplace_back(l1, pos); swap(p[l1], p[pos]); int l2 = sim(p, x); if (p[l2] != x){ int pos1 = find(p.begin(), p.end(), x) - p.begin(); if (pos1 != l2){ ops.emplace_back(l2, pos1); swap(p[l2], p[pos1]); } } cout << ops.size() << "\n"; for (auto &[i, j] : ops){ cout << i + 1 << " " << j + 1 << "\n"; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); tc{ solve(); }; return 0; }В этом коде исправлены следующие моменты:
- Индексация массива
pведётся с 0, поэтому в функцииsimи везде по коду соответствующие индексы тоже начинаются с 0. - Функция
simтеперь корректно работает с индексами от 0 доn, что соответствует 0-индексации в C++. - При выводе ответов к индексам элементов добавляется 1 (поскольку в задаче нумерация позиций начинается с 1).
Теперь код должен корректно решать задачу и проходить все тесты.
- Индексация массива