제출 #421734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421734		Pbezz	정렬하기 (IOI15_sorting)	C++14	0 / 100	8 ms	460 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,a,b;
	bool ok=true;
	for(i=0;i<N;i++){
	if(S[i]!=i)ok=false;
	}
	if(ok)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;
swap(S[X[i]], S[Y[i]]);
//swap( fim[X[i]], fim[Y[i]] );

	for(k=0;k<N;k++){

	if(fim[k]==X[i]){
	a=k;
	}
	if(fim[k]==Y[i]){
	b=k;
	}

	}

swap( fim[a], fim[b] );


	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







}

while(R<M){
swap(S[X[R]], S[Y[R]]);
P[R]=0;
Q[R]=0;
R++;

}/*
for(j=0;j<N;j++){
cout<<S[j]<<" ";
}cout<<endl<<endl;
*/



	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