Submission #45321886

---

Source Code Expand

#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

void solve() {
	int n;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		--p[i];
	}
	vector<pair<int, int>> ans;
	set<int> left, right;
	for (int i = 0; i < n; ++i) {
		left.emplace(i);
		right.emplace(i);
	}
	while (true) {
		while (!left.empty() && p[*left.begin()] >= *left.begin()) {
			left.erase(left.begin());
		}
		if (left.empty()) {
			break;
		}
		int l = *left.begin();

		vector<int> go;
		int x = p[l];
		go.push_back(x);
		while (p[x] < l) {
			x = p[x];
			go.push_back(x);
		}
		go.push_back(l);
		for (int i = go.size() - 1; i > 0; --i) {
			ans.emplace_back(go[i - 1], go[i]);
			swap(p[go[i - 1]], p[go[i]]);
		}
		if (p[l] == l) {
			ans.emplace_back(0, 0);
		} else {
			right.emplace(l);
		}


		while (!right.empty() && p[*right.rbegin()] <= *right.rbegin()) {
			right.erase(*right.rbegin());
		}
		if (right.empty()) {
			break;
		}
		int r = *right.rbegin();

		go.clear();
		x = p[r];
		go.push_back(x);
		while (p[x] > r) {
			x = p[x];
			go.push_back(x);
		}
		go.push_back(r);
		for (int i = go.size() - 1; i > 0; --i) {
			ans.emplace_back(go[i - 1], go[i]);
			swap(p[go[i - 1]], p[go[i]]);
		}
		if (p[r] == r) {
			ans.emplace_back(0, 0);
		} else {
			left.emplace(r);
		}
	}
	for (int i = 0; i < n; ++i) {
		assert(p[i] == i);
	}
	if (!ans.empty()) {
		assert(ans.back() == std::pair(0, 0));
		ans.pop_back();
	}
	assert(ans.size() <= n - 1);
	for (int i = 0; i + 1 < ans.size(); ++i) {
		assert(ans[i].second <= ans[i + 1].first || ans[i + 1].second <= ans[i].first);
	}
	cout << ans.size() << "\n";
	for (auto [l, r]: ans) {
		if (l > r) {
			swap(l, r);
		}
		cout << l + 1 << " " << r + 1 << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	int tt;
	cin >> tt;
	for (int i = 0; i < tt; ++i) {
		solve();
	}
	return 0;
}

Submission Info

Compile Error

In file included from /usr/include/c++/12/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:33,
                 from Main.cpp:4:
Main.cpp: In function ‘void solve()’:
Main.cpp:100:27: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  100 |         assert(ans.size() <= n - 1);
      |                ~~~~~~~~~~~^~~~~~~~
Main.cpp:101:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  101 |         for (int i = 0; i + 1 < ans.size(); ++i) {
      |                         ~~~~~~^~~~~~~~~~~~

Judge Result