Submission #135972

#	Time	Username	Problem	Language	Result	Execution time	Memory
135972		amiratou	Sorting (IOI15_sorting)	C++14	20 / 100	20 ms	11384 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int tab[15005][505];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	for (int i = 0; i < N; ++i)
		tab[M-1][i]=i,tab[M][i]=i;
	map<int,int> pos;
	for (int i = 0; i < N; ++i)
		pos[S[i]]=i;
	for (int i = M-1; i >=0 ; i--)
	{
		swap(tab[i][X[i]],tab[i][Y[i]]);
		if(i)
			for (int j = 0; j < N; ++j)
				tab[i-1][j]=tab[i][j];
	}
	for (int i = 0; i < M; ++i)
	{
		bool sorted=1;
		for (int j = 0; j < N; ++j)
			if(tab[M][j]!=S[j]){sorted=0;break;}
		if(sorted)return i;
		P[i]=Q[i]=0;
		swap(pos[S[X[i]]],pos[S[Y[i]]]);
		swap(S[X[i]],S[Y[i]]);
		sorted=1;
		for (int j = 0; j < N; ++j)
			if(tab[M][j]!=S[j]){sorted=0;break;}
		if(sorted)return i+1;
		if(i==(M-1)){
			for (int j = 0; j < N; ++j)
				if(tab[i+1][j]!=S[j]){
					P[i]=j,Q[i]=pos[tab[i+1][j]];
					swap(pos[S[P[i]]],pos[S[Q[i]]]);
					swap(S[P[i]],S[Q[i]]);
					break;
				}
			continue;
		}
		if(tab[i+1][X[i+1]]!=S[X[i+1]]){
			P[i]=X[i+1],Q[i]=pos[tab[i+1][X[i+1]]];
			swap(pos[S[P[i]]],pos[S[Q[i]]]);
			swap(S[P[i]],S[Q[i]]);
		}
		else if(tab[i+1][Y[i+1]]!=S[Y[i+1]]){
			P[i]=Y[i+1],Q[i]=pos[tab[i+1][Y[i+1]]];
			swap(pos[S[P[i]]],pos[S[Q[i]]]);
			swap(S[P[i]],S[Q[i]]);
		}
		else{
			for (int j = 0; j < N; ++j)
				if(tab[i+1][j]!=S[j]){
					P[i]=j,Q[i]=pos[tab[i+1][j]];
					swap(pos[S[P[i]]],pos[S[Q[i]]]);
					swap(S[P[i]],S[Q[i]]);
					break;
				}
		}
	}
	return M;
}

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