Submission #228657

#	Time	Username	Problem	Language	Result	Execution time	Memory
228657		pit4h	Sorting (IOI15_sorting)	C++14	36 / 100	6 ms	640 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<n; ++i) {
		//~ cerr<<t[i]<<' ';
	//~ }
	//~ cerr<<'\n';
	for(int i=0; i<len; ++i) {
		swap(t[x[i]], t[y[i]]);
	}
	vector<int> wrong, pos(n), fin(n), where(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;
	}
	for(int i=0; i<n; ++i) {
		fin[i]=pos[t[i]];
		where[pos[t[i]]]=i;
	}
	for(int i=0; i<n; ++i) {
		t[i]=s[i];
	}
	//~ cerr<<"fin: ";
	//~ for(int i=0; i<n; ++i) cerr<<where[i]<<' ';
	//~ cerr<<'\n';
	//~ cerr<<"wrong: ";
	//~ for(int i: wrong) cerr<<i<<' ';
	//~ cerr<<'\n';
	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]]]);
		swap(fin[where[x[i]]], fin[where[y[i]]]);
		swap(where[x[i]], where[y[i]]);
		while(wrong.size() && fin[pos[wrong.back()]]==wrong.back()) {
			wrong.pop_back();
		}
		if(wrong.empty()) break;
		int u = wrong.back();
		wrong.pop_back();
		//~ cerr<<len-i<<' '<<u<<' '<<pos[u]<<' '<<fin[u]<<'\n';
		p[i]=pos[u];
		q[i]=fin[u];
		swap(t[p[i]], t[q[i]]);
		swap(pos[t[p[i]]], pos[t[q[i]]]);
	}
	//~ cerr<<len<<'\n';
	//~ for(int i=0; i<len; ++i) {
		//~ cerr<<p[i]<<' '<<q[i]<<'\n';
	//~ }
	//~ for(int i=0; i<len; ++i) {
		//~ swap(s[x[i]], s[y[i]]);
		//~ swap(s[p[i]], s[q[i]]);
	//~ }
	//~ for(int i=0; i<n; ++i) {
		//~ cerr<<s[i]<<' ';
	//~ }
	//~ cerr<<'\n';
	return len;
}

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