Submission #1088691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088691		gustavo_d	Sorting (IOI15_sorting)	C++17	20 / 100	1092 ms	604 KiB

sorting

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

int findSwapPairs(
	int N, int S[], int M, int X[], int Y[], int P[], int Q[]
) {
	if (N == 1) return 0;
	vector<int> s(N);
	for (int i=0; i<N; i++) s[i] = S[i];

	vector<int> p_ans(M), q_ans(M);
	for (int ops=0; ops<=M; ops++) {
		for (int i=0; i<N; i++) S[i] = s[i];
		vector<int> p, q;
		int m = ops;
		int pt = 0;
		int t=0;
	    for (; t<m and pt < N; t++, pt++) {
	    	bool sorted = true;
			for (int i=1; i<N; i++) {
				if (S[i] < S[i-1]) sorted = false;
			}
			if (sorted) break;

			swap(S[X[t]], S[Y[t]]);

	    	int permut[N];
	    	for (int i=0; i<N; i++) permut[i] = i;
	    	for (int i=t+1; i<m; i++) {
	    		swap(permut[X[i]], permut[Y[i]]);
	    	}
	    	int a=0, b=0;
	    	for (int i=0; i<N; i++) {
	    		if (S[i] == pt) a = i;
	    	}
	    	b = permut[pt];
	    	if (a == b) {
	    		t--;
	    		continue;
	    	}
	    	swap(S[a], S[b]);
	    	p.push_back(a);
	    	q.push_back(b);
	    }

    	bool sorted = true;
		for (int i=1; i<N; i++) {
			if (S[i] < S[i-1]) sorted = false;
		}
		if (!sorted) continue;
	    // cout << "ans = ";
	    // for (int i=0; i<N; i++) cout << S[i] << ' ';
	    // cout << endl;

	    if (p.size() <= p_ans.size()) {
	    	swap(p, p_ans);
	    	swap(q, q_ans);
	    }
	}
	for (int i=0; i<(int)p_ans.size(); i++) {
		P[i] = p_ans[i];
		Q[i] = q_ans[i];
	}
	return (int)p_ans.size();
}

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