Submission #228661

#	Time	Username	Problem	Language	Result	Execution time	Memory
228661		pit4h	Sorting (IOI15_sorting)	C++14	100 / 100	206 ms	29660 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int dfs(int x, vector<int>& g, vector<bool>& vis) {
	vis[x]=1;
	if(!vis[g[x]]) {
		return dfs(g[x], g, vis)+1;
	}
	return 1;
}
void dfsv(int x, vector<int>& g, vector<bool>& vis, vector<int>& vec) {
	vis[x]=1;
	vec.push_back(x);
	if(!vis[g[x]]) {
		dfsv(g[x], g, vis, vec);
	}
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    vector<int> t;
    for(int i=0; i<n; ++i) {
		t.push_back(s[i]);
	}
	int lo = 0, hi = m, len=m;
	while(lo<=hi) {
		int l = (lo+hi)/2;
		vector<bool> vis(n);
		for(int i=0; i<n; ++i) {
			t[i]=s[i];
		}
		for(int i=0; i<l; ++i) {
			swap(t[x[i]], t[y[i]]);
		}
		int cnt=0;
		for(int i=0; i<n; ++i) {
			if(!vis[i]) {
				cnt += dfs(i, t, vis)-1;
			}
		}
		if(cnt<=l) {
			len=l;
			hi=l-1;
		}
		else {
			lo=l+1;
		}
	}
	for(int i=0; i<n; ++i) {
		t[i]=s[i];
	}
	for(int i=0; i<len; ++i) {
		swap(t[x[i]], t[y[i]]);
	}
	vector<int> wrong, pos(n), T=t, POS(n);
	vector<bool> vis(n);
	for(int i=0; i<n; ++i) {
		if(t[i]!=i && !vis[i]) {
			vector<int> vec;
			dfsv(i, t, vis, vec);
			reverse(vec.begin(), vec.end());
			for(int j: vec) wrong.push_back(t[j]);
		}
		pos[s[i]]=i;
		POS[t[i]]=i;
	}
	for(int i=0; i<n; ++i) {
		t[i]=s[i];
	}
	for(int i=0; i<len; ++i) {
		p[i]=q[i]=0;
	}
	reverse(wrong.begin(), wrong.end());
	for(int i=0; i<len; ++i) {
		swap(t[x[i]], t[y[i]]);
		swap(pos[t[x[i]]], pos[t[y[i]]]);
		while(wrong.size() && T[wrong.back()]==wrong.back()) { // update
			wrong.pop_back();
		}
		if(wrong.empty()) break;
		int u = wrong.back();
		wrong.pop_back();
		p[i]=pos[u];
		q[i]=pos[T[u]];
		swap(t[p[i]], t[q[i]]);
		swap(pos[t[p[i]]], pos[t[q[i]]]);
		swap(T[POS[u]], T[u]); // zamień miejscami gościa z wartością 'u' i gościa, który na końcu jest na pozycji 'u'
		swap(POS[u], POS[T[u]]);
	}
	return len;
}

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