Submission #1222627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222627		HossamHero7	Sorting (IOI15_sorting)	C++20	16 / 100	1 ms	328 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "sorting.h"
// #include "grader.cpp"

int findSwapPairs(int n, int s[], int m, int X[], int Y[], int P[], int Q[]) {
    vector<int> tar(n);
	iota(tar.begin(),tar.end(),0);
	for(int i=0;i<n;i++) P[i] = Q[i] = 0;
	vector<int> tmp(n);
	for(int i=0;i<n;i++) tmp[i] = s[i];
	for(int i=n-1;i>=0;i--){
		swap(tar[X[i]],tar[Y[i]]);
	}
	// for(auto i : tar) cout<<i<<' ';
	// cout<<endl;
	vector<int> idx(n);
	for(int i=0;i<n;i++){
		idx[s[i]] = i;
	}
	auto do_swap = [&](int i,int j){
		int x = s[i] , y = s[j];
		swap(s[i],s[j]);
		swap(idx[x],idx[y]);
	};
	int pt = 0;
	for(int i=0;i<n;i++){
		do_swap(X[i],Y[i]);
		swap(tar[X[i]],tar[Y[i]]);
		while(pt < n && s[pt] == tar[pt]) pt ++;
		if(pt != n) P[i] = pt , Q[i] = idx[tar[pt]] , do_swap(pt,idx[tar[pt]]);
	}
	for(int i=0;i<n;i++) {
		swap(tmp[X[i]],tmp[Y[i]]);
		swap(tmp[P[i]],tmp[Q[i]]);
	}
	// for(auto i : tmp) cout<<i<<' ';
	// cout<<endl;
	return n;
}

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