Submission #302425

#	Time	Username	Problem	Language	Result	Execution time	Memory
302425		bensonlzl	Sorting (IOI15_sorting)	C++14	100 / 100	433 ms	27152 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

int n, m, x[600005], y[600005], s[600005];

vector<pi> swaps;

bool sortable(int limit){
	//cerr << "STARTING " << limit << '\n';
	swaps.clear();
	vector<int> p(n), rev(n);
	vector<int>	fp(n);
	vector<int> vis(n,0);
	vector<pi> temp;
	for (int i = 0; i < n; ++i){
		p[i] = i;
	}
	for (int i = 0; i < limit; ++i){
		swap(p[x[i]],p[y[i]]);
	}
	for (int i = 0; i < n; ++i){
		fp[i] = s[p[i]];
	}
	for (int i = 0; i < n; ++i){
		if (!vis[i]){
			vis[i] = 1;
			int idx = fp[i];
			while (idx != i){
				vis[idx] = 1;
				temp.push_back(pi(idx,fp[idx]));
				idx = fp[idx];
			}
		}
	}
	if ((int) temp.size() > limit) return false;
	while ((int) temp.size() < limit) temp.push_back(pi(0,0));
	for (int i = 0; i < n; ++i){
		p[i] = s[i];
		rev[s[i]] = i;
	}
	for (int i = 0; i < limit; ++i){
		//cerr << x[i] << ' ' << y[i] << '\n';
		swap(rev[p[x[i]]],rev[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
		//for (auto it : p) cerr << it << ' ';
		//cerr << '\n';
		int s1 = rev[temp[i].first], s2 = rev[temp[i].second];
		//cerr << s1 << ' ' << s2 << '\n';
		swaps.push_back(pi(s1,s2));
		swap(rev[p[s1]],rev[p[s2]]);
		swap(p[s1],p[s2]);
		//for (auto it : p) cerr << it << ' ';
		//cerr << '\n';
	}
	return true;
}

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 ans = 0;
    if (sortable(0)) return 0;
    for (int i = 19; i >= 0; --i){
		int test = ans + (1 << i);
		if (test > M) continue;
		if (!sortable(test)) ans = test;
	}
	ans++;
	sortable(ans);
    for (int i = 0; i < ans; ++i){
		P[i] = swaps[i].first;
		Q[i] = swaps[i].second;
	}
	return ans;
}

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