Submission #362611

#	Time	Username	Problem	Language	Result	Execution time	Memory
362611		NachoLibre	Sorting (IOI15_sorting)	C++17	100 / 100	296 ms	33184 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include "sorting.h"
#else
#endif

const int N = 200005, M = 600005;
int n, m, s[N], x[M], y[M], c[N], d[N];

inline void S(int x, int y) {
	d[c[x]] = y;
	d[c[y]] = x;
	swap(c[x], c[y]);
}

void Gc() {
	for(int i = 0; i < n; ++i) {
		c[i] = s[i];
		d[s[i]] = i;
	}
}

vector<pair<int, int>> C(int a) {
	vector<pair<int, int>> dr(1, {0, 0});
	Gc();
	for(int i = 0; i < a; ++i) {
		S(x[i], y[i]);
	}
	for(int i = 0; i < n; ++i) {
		if(c[i] != i) {
			if(sz(dr) == a + 1) {
				dr[0].first = 12321;
				break;
			}
			dr.push_back({i, c[i]});
			S(i, d[i]);
		}
	}
	while(dr.size() < a + 1) {
		dr.push_back({0, 0});
	}
	return dr;
}

vector<pair<int, int>> D(vector<pair<int, int>> v) {
	vector<pair<int, int>> dr;
	Gc();
	for(int i = 1; i < sz(v); ++i) {
		S(x[i - 1], y[i - 1]);
		dr.push_back({d[v[i].first], d[v[i].second]});
		S(d[v[i].first], d[v[i].second]);
	}
	return dr;
}

int findSwapPairs(int _n, int _s[], int _m, int _x[], int _y[], int p[], int q[]) {
	n = _n; m = _m;
	for(int i = 0; i < n; ++i) {
		s[i] = _s[i];
	}
	for(int i = 0; i < m; ++i) {
		x[i] = _x[i];
		y[i] = _y[i];
	}
	int l = 0, r = m;
	while(l < r) {
		int md = (l + r) / 2;
		if(C(md)[0].first) {
			l = md + 1;
		} else {
			r = md;
		}
	}
	vector<pair<int, int>> ve = C(l);
	vector<pair<int, int>> mo = D(ve);
	for(int i = 0; i < sz(mo); ++i) {
		p[i] = mo[i].first;
		q[i] = mo[i].second;
	}
	return sz(mo);
}

#ifdef wambule
int nn = 5;
int mm = 5;
int ss[] = {3, 0, 4, 2, 1};
int xx[] = {1, 4, 2, 1, 0};
int yy[] = {1, 0, 3, 4, 4};
int p[M], q[M];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int k = findSwapPairs(nn, ss, mm, xx, yy, p, q);
	cout << k << endl;
	for(int i = 0; i < k; ++i) {
		cout << p[i] << " " << q[i] << endl;
	}
	return 0;
}
#endif

Compilation message (stderr)

sorting.cpp: In function 'void S(int, int)':
sorting.cpp:13:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   13 | inline void S(int x, int y) {
      |                           ^
sorting.cpp:11:23: note: shadowed declaration is here
   11 | int n, m, s[N], x[M], y[M], c[N], d[N];
      |                       ^
sorting.cpp:13:27: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   13 | inline void S(int x, int y) {
      |                           ^
sorting.cpp:11:17: note: shadowed declaration is here
   11 | int n, m, s[N], x[M], y[M], c[N], d[N];
      |                 ^
sorting.cpp: In function 'std::vector<std::pair<int, int> > C(int)':
sorting.cpp:42:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  while(dr.size() < a + 1) {
      |        ~~~~~~~~~~^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26