Submission #1242691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242691		adriines06	Sorting (IOI15_sorting)	C++20	100 / 100	184 ms	17908 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>s,x,y;
vector<pair<int,int>>ans;
bool ver(int r, vector<int>val){
	ans.clear();
	ans.assign(r,{0,0});
	vector<int>valf(n),posf(n),pos(n);
	for(int i=0;i<n;i++){
		posf[val[i]]=i;
		valf[i]=val[i];
		pos[val[i]]=i;
	}
	//simular E 
	for(int i=0;i<r;i++){
		swap(posf[valf[x[i]]],posf[valf[y[i]]]); ///pos[valor final]=indice final
		swap(valf[x[i]],valf[y[i]]); // valf[indice final]=valorfinal
	}
	//armar
	int p=0;
	for(int i=0;i<r;i++){
		swap(pos[val[x[i]]],pos[val[y[i]]]); //pos[valor]=indice actual
		swap(val[x[i]],val[y[i]]); //val[indice actual]=valor

		while(p<n && p==valf[p]){
			p++;
		}
		if(p==n) break;
		//cambio
		//p(indice==valor) valf[p]-> el que llegara ahi
		pair<int,int>c={pos[p],pos[valf[p]]}; //el que tiene que estar en p con el que esta al final
		ans[i]=c;
		swap(pos[p],pos[valf[p]]);
		swap(val[c.first],val[c.second]);
		//cambios al final

		valf[posf[p]]=valf[p];
		posf[valf[p]]=posf[p];
		valf[p]=p;
	}
	while(p<n && val[p]==pos[val[p]]){
		p++;
	}
	return p==n;

}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N;
	s.resize(n);
	x.resize(M);
	y.resize(M);
	for(int i=0;i<M;i++){
		x[i]=X[i];
		y[i]=Y[i];
	}
	for(int i=0;i<n;i++){
		s[i]=S[i];
	}
	int l=0,r=M;
	int cont=0;
	while(l<r){
		int mid=(r+l)/2;
		if(ver(mid,s)){
			r=mid;
		}
		else{
			l=mid+1;
		}
		cont++;
	}
	if(ver(l,s)){
		for(int i=0;i<l;i++){
		P[i]=ans[i].first;
		Q[i]=ans[i].second;
		}
	}
	return l;
}

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