제출 #1247073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247073		countless	Sorting (IOI15_sorting)	C++20	36 / 100	1093 ms	4308 KiB

sorting

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	// insertion sort.
	vector<int> A(N), at(N);
	for (int i = 0; i < N; i++) {
		A[i] = S[i];
		at[A[i]] = i;
	}

	for (auto &x : A) cerr << x << " ";
	cerr << endl;

	int r = 0;
	for (int i = N-1; i >= 0; i--) {
		if (A[i] == i) continue;

		cerr << "ele:" sp A[i] sp "at" sp i << endl;

		// perform X[i], Y[i] swap
		swap(at[A[X[i]]], at[A[Y[i]]]);
		swap(A[X[i]], A[Y[i]]);

		cerr << "ermek:" sp A[X[i]] sp "and" sp A[Y[i]] << endl;

		// we don't really need to save swaps for st1-3 for now
		int at1 = at[i], at2 = i;
		int el1 = A[at[i]], el2 = A[i];

		P[r] = at1, Q[r] = at2;
		r++;

		swap(at[el1], at[el2]);
		swap(A[at1], A[at2]);

		cerr << "aizhan:" sp el1 sp "and" sp el2 << endl;


		for (auto &x : A) cerr << x << " ";
		cerr << endl;
	}

	return r;
}

// 3 0 4 2 1
// 

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