Submission #1286784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286784		Faisal_Saqib	Sorting (IOI15_sorting)	C++20	54 / 100	3 ms	832 KiB

sorting

#include "sorting.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+100;
int p[N],ind[N];
bool vis[N];
int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]) {
	if(is_sorted(s,s+n))
		return 0;
	for(int i=0;i<n;i++)vis[i]=0,p[i]=s[i];
	for(int i=0;i<m;i++)
	{
		swap(p[x[i]],p[y[i]]);
	}
	// cout<<"CALLED "<<endl;
	// cout<<"FNL: ";
	// for(int i=0;i<n;i++)cout<<p[i]<<' ';
	// cout<<endl;
	vector<pair<int,int>> req;
	for(int i=0;i<n;i++)
	{
		if(vis[i])continue;
		int j=i;
		vector<int> cyc;
		while(!vis[j])
		{
			cyc.push_back(j);
			vis[j]=1;
			j=p[j];
		}
		for(int i=1;i<cyc.size();i++)
		{
			req.push_back({p[cyc[i-1]],p[cyc[i]]});
		}
		// cout<<"Cycle ";
		// for(auto x:cyc)cout<<x<<' ';
		// cout<<endl;
	}
	for(int i=0;i<n;i++)p[i]=s[i],ind[s[i]]=i;
	for(int i=0;i<m;i++)P[i]=0,Q[i]=0;
	// if(req.size()>m)
	// {
	// 	return 0;
	// }
	for(int i=0;i<req.size();i++)
	{
		swap(ind[p[x[i]]],ind[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
		P[i]=ind[req[i].first],Q[i]=ind[req[i].second];
		swap(ind[p[P[i]]],ind[p[Q[i]]]);
		swap(p[P[i]],p[Q[i]]); 
		if(is_sorted(p,p+n))
			return i+1;
		// swap()
	}
	for(int i=req.size();i<m;i++)
	{
		swap(ind[p[x[i]]],ind[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
		if(is_sorted(p,p+n))
			return i+1;
	}
	// for(int i=0;i<n;i++)
	// {
	// 	if(p[i]!=i)
	// 	{
	// 		// return 0;
	// 		exit(-1);
	// 	}
	// }
	return m;
}

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