Submission #832675

#	Time	Username	Problem	Language	Result	Execution time	Memory
832675		AkramElOmrani	정렬하기 (IOI15_sorting)	C++17	54 / 100	206 ms	720 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[]) {
	int ans = 0;
	for(int round = 0; round < m; ++round) {
		if(is_sorted(s, s + n)) {
			return ans;
		}
		swap(s[x[round]], s[y[round]]);
		// we assume that after m rounds it will def be swapped
		vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
		// ord[i] = i; at last since it's sorted
		for(int j = m - 1; j > round; --j) {
			swap(ord[x[j]], ord[y[j]]);
		}

		for(int i = 0; i < n; ++i) {
			if(s[i] != ord[i]) { // ith element isn't in its place look for who is in its place
				for(int k = i + 1; k < n; ++k) {
					if(s[k] == ord[i]) {
						swap(s[k], s[i]);
						p[ans] = k;
						q[ans] = i;
						goto end;
					}
				}
			}
		}
		p[ans] = q[ans] = n - 1; // already sorted no change needed
		end:;
		++ans;
	}
	return ans;
}

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