Submission #1237452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237452		crispxx	Sorting (IOI15_sorting)	C++20	74 / 100	1096 ms	35644 KiB

sorting

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
	vector<int> comp(n);
	
	for(int i = 0; i < n; i++) comp[i] = s[i];
	
	sort(all(comp));
	comp.erase(unique(all(comp)), comp.end());
	
	for(int i = 0; i < n; i++) s[i] = lower_bound(all(comp), s[i]) - comp.begin();
	
	vector<int> pos(n), ele(n), a(n);
	
	vector<pair<int, int>> a1(n);
	
	for(int i = 0; i < n; i++) {
		a[i] = s[i];
		a1[i] = {s[i], i};
	}
	
	auto b = a;
	sort(all(b));
	
	auto b1 = a1;
	sort(all(b1));
	
	auto check = [&](int R) {
		for(int i = 0; i < n; i++) a[i] = s[i];
		
		for(int i = 0; i < R; i++) swap(a[x[i]], a[y[i]]);
		
		vector<vector<int>> A(n), B(n);
		
		for(int i = 0; i < n; i++) {
			if(a[i] == b[i]) pos[i] = i;
			else A[a[i]].pb(i), B[b[i]].pb(i);
		}
		
		for(int i = 0; i < n; i++) {
			auto &val = A[i];
			auto &val2 = B[i];
			assert(val.size() == val2.size());
			for(int j = 0; j < (int)val.size(); j++) {
				pos[val[j]] = val2[j];
			}
		}
		
		int cnt = 0;
		
		for(int i = 0; i < n; i++) {
			int j = i;
			while(j != pos[j]) {
				int k = pos[j];
				swap(a[j], a[k]);
				swap(pos[j], pos[k]);
				cnt++;
			}
		}
		
		return cnt <= R;
	};
	
	int l = 0, r = m;
	
	while(l < r) {
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	
	auto construct = [&](int R) {
		for(int i = 0; i < n; i++) a1[i] = {s[i], i};
		
		for(int i = 0; i < R; i++) swap(a1[x[i]], a1[y[i]]);
		
		vector<vector<int>> A(n), B(n);
		
		for(int i = 0; i < n; i++) {
			int key1 = a1[i].first;
			int key2 = b1[i].first;
			if(key1 == key2) pos[i] = i;
			else A[key1].pb(i), B[key2].pb(i);
		}
		
		for(int i = 0; i < n; i++) {
			auto &val = A[i];
			auto &val2 = B[i];
			assert(val.size() == val2.size());
			for(int j = 0; j < (int)val.size(); j++) {
				pos[val[j]] = val2[j];
			}
		}
		
		vector<pair<int, int>> idx;
		
		for(int i = 0; i < n; i++) {
			int j = i;
			while(j != pos[j]) {
				int k = pos[j];
				idx.pb({ a1[j].second, a1[k].second });
				// idx.pb({ j, k });
				swap(a1[j], a1[k]);
				swap(pos[j], pos[k]);
			}
		}
		
		assert( (int)idx.size() <= R );
		
		while( (int)idx.size() < R ) idx.pb({0, 0});
		
		// for(auto [i, j] : idx) {
			// cout << i << ' ' << j << nl;
		// }
		
		// cout << nl;
		
		// cout << "INIT: " << nl;
		
		// for(int j = 0; j < n; j++) cout << j << ' ';
		// cout << nl;
		
		// for(int j = 0; j < n; j++) cout << s[j] << ' ';
		// cout << nl;
		
		iota(all(ele), 0);
		iota(all(pos), 0);
		
		for(int i = 0; i < R; i++) {
			// cout << nl;
			// for(auto j : pos) cout << j << ' ';
			// cout << nl;
			
			// swap( s[x[i]], s[y[i]] );
			
			int ok1 = ele[x[i]], ok2 = ele[y[i]];
			
			swap(ele[x[i]], ele[y[i]]);
			swap( pos[ok1], pos[ok2] );
			
			// for(auto j : pos) cout << j << ' ';
			// cout << nl;
			
			// cout << nl;
			
			// for(int j = 0; j < n; j++) cout << s[j] << ' ';
			// cout << nl;
			
			auto [i1, i2] = idx[i];
			
			ok1 = pos[i1], ok2 = pos[i2];
			
			p[i] = ok1, q[i] = ok2;
			
			// swap( s[ok1], s[ok2] );
			
			swap( ele[ok1], ele[ok2] );
			swap( pos[i1], pos[i2] );
			
			// for(int j = 0; j < n; j++) cout << s[j] << ' ';
			// cout << nl;
		}
	};
	
	// cout << nl;
	
	construct(l);
	
	return l;
}

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