제출 #832684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832684		AkramElOmrani	정렬하기 (IOI15_sorting)	C++17	54 / 100	238 ms	616 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]]);
		}
		vector<int> inv_s(n);
		for(int i = 0; i < n; ++i) {
			inv_s[s[i]] = i;
		}
		for(int i = 0; i < n; ++i) {
			if(s[i] != ord[i]) {
				int k = inv_s[ord[i]];
				swap(s[k], s[i]);
				p[ans] = k;
				q[ans] = i;
				goto end;
			}
		}
		// 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