Submission #421712

#	Time	Username	Problem	Language	Result	Execution time	Memory
421712		Pbezz	Sorting (IOI15_sorting)	C++14	0 / 100	3 ms	332 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN=2e5+5;
const ll INF=1e9+7;



int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int i,k,j,R=0;
	bool ok=true;
	for(i=0;i<N;i++){
	if(S[i]!=i)ok=false;
	}
	if(ok)return 0;

	swap(S[X[0]],S[Y[0]]);

	ok=true;
	for(i=0;i<N;i++){
	if(S[i]!=i)ok=false;
	}
	if(ok){
	P[R]=0;	Q[R]=0;	R++;
	return 0;
	}

	int fim[N];

	for(i=0;i<N;i++)fim[i]=i;

	for(j=0;j<M;j++){
	swap( fim[X[j]], fim[Y[j]] );
	}

	//fim[i] e a pos inicial que vai acabar em i

	for(i=0;i<N;i++){//fixar o i
//ver pos que faz com que o i acabe bem
//que e fim[i]
//cout<<i<<endl;
	for(k=0;k<N;k++){
	if(S[k]==i)break;
	}
/*
for(j=0;j<N;j++){
cout<<fim[j]<<" ";
}cout<<endl<<endl;
*/

P[R]=fim[i];
Q[R]=k;
R++;
swap(S[fim[i]],S[k]);

//atualizar fim

	swap( fim[X[i+1]], fim[Y[i+1]] );





}

while(R<M){

P[R]=0;
Q[R]=0;
R++;

}




	return R;
}

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