Submission #676034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
676034	2022-12-29T01:24:01 Z	atcgu	Sorting (IOI15_sorting)	C++14	Compilation error	0 ms	0 KB

sorting

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;

typedef pair<int, int> ii;
typedef long long ll;

int n, m;
vector<int> ar;

int ar1[MAXN], ar2[MAXN];

vector<ii> ans;

bool check(int t) {
	vector<int> cur = ar;
	for (int i = 0; i < t; i++) {
		swap(cur[ar1[i]], cur[ar2[i]]);
	}
	vector<ii> swaps;
	for (int i = 0; i < n; i++) {
		while (cur[i] != i) {
			swaps.emplace_back(cur[i], cur[cur[i]]);
			swap(cur[i], cur[cur[i]]);
		}
	}
	while (swaps.size() < t) swaps.emplace_back(0, 0);
	if (swaps.size() > t) return false;
	cur = ar;
	vector<int> ind(n);
	for (int i = 0; i < n; i++) {
		ind[cur[i]] = i;
	}
	vector<ii> ret;
	for (int i = 0; i < t; i++) {
		int x = ar1[i];
		int y = ar2[i];
		swap(ind[cur[x]], ind[cur[y]]);
		swap(cur[x], cur[y]);

		x = swaps[i].first;
		y = swaps[i].second;
		ret.emplace_back(ind[x], ind[y]);
		swap(cur[ind[x]], cur[ind[y]]);
		swap(ind[x], ind[y]);
	}
	ans = ret;
	return true;
}

int main() {
	cin >> n;
	ar = vector<int>(n);
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
	}
	cin >> m;
	int sw = 0;
	for (int i = 0; i < m; i++) {
		cin >> ar1[i] >> ar2[i];
	}
	int lo = 0, hi = m;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		}
		else lo = mid + 1;
	}
	check(lo);
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}

Compilation message

sorting.cpp: In function 'bool check(int)':
sorting.cpp:29:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  while (swaps.size() < t) swaps.emplace_back(0, 0);
      |         ~~~~~~~~~~~~~^~~
sorting.cpp:30:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if (swaps.size() > t) return false;
      |      ~~~~~~~~~~~~~^~~
sorting.cpp: In function 'int main()':
sorting.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i = 0; i < ans.size(); i++) {
      |                  ~~^~~~~~~~~~~~
sorting.cpp:60:6: warning: unused variable 'sw' [-Wunused-variable]
   60 |  int sw = 0;
      |      ^~
/usr/bin/ld: /tmp/ccML9Zp5.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqP3z48.o:sorting.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccML9Zp5.o: in function `main':
grader.c:(.text.startup+0x4eb): undefined reference to `findSwapPairs(int, int*, int, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status