Submission #99158

#	Time	Username	Problem	Language	Result	Execution time	Memory
99158		Lawliet	Sorting (IOI15_sorting)	C++14	0 / 100	85 ms	46652 KiB

sorting

#include <bits/stdc++.h>

#define MAX 2010

using namespace std;

int n, m;

int aux[MAX];
int numSwaps[MAX][2];
int version[3*MAX][MAX];

/*int s[MAX];
int x[MAX];
int y[MAX];
int p[MAX];
int q[MAX];*/

bool marc[MAX];

int find_next(int i)
{
	for(int g = 1 ; g <= n ; g++) 
		if(aux[g] == i) return g;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	n = N;
	m = M;
	
	for(int g = n ; g > 0 ; g--) S[g] = S[g - 1] + 1;
	for(int g = m ; g > 0 ; g--) X[g] = X[g - 1] + 1;
	for(int g = m ; g > 0 ; g--) Y[g] = Y[g - 1] + 1;
	
	for(int g = 1 ; g <= n ; g++) version[0][S[g]] = g;
	
	for(int k = 1 ; k <= M ; k++)
	{
		for(int g = 1 ; g <= n ; g++) version[k][g] = version[k - 1][g];
		
		int i, j;
		
		for(int h = 1 ; h <= n ; h++)
		{
			for(int l = 0 ; l < 2 ; l++)
			{
				if(version[k][h] == X[k]) i = h;
				if(version[k][h] == Y[k]) j = h;
			}
		}
		
		swap(version[k][i] , version[k][j]);
		
		//printf("p ");
		//for(int g = 1 ; g <= n ; g++) printf("%d ",version[k][g]);
		//printf("\n");
	}
	
	int ans = -1;
	
	for(int k = 1 ; k <= M && ans == -1 ; k++)
	{
		memset(marc , false , sizeof(marc));
		
		int cycles = 0;
		
		for(int g = 1 ; g <= n ; g++)
		{
			if(marc[g]) continue;
			
			int cur = g;
			
			while(!marc[cur])
			{
				marc[cur] = true;
				cur = version[k][cur];
			}
			
			cycles++;
		}
		
		if(n - cycles <= k) ans = k;
	}
	
	//printf("ans = %d\n",ans);
	
	for(int g = 1 ; g <= n ; g++) aux[g] = version[ans][g];
	//version[k][i] = dps do kº-ésimo movimento do cara, qual é o índice do valor i
	
	int cnt = 0;
	
	for(int g = 1 ; g <= n ; g++)
	{
		//printf("o ");
		//for(int h = 1 ; h <= n ; h++) printf("%d ",aux[h]);
		//printf("\n");
		
		if(aux[g] == g) continue;
				
		numSwaps[cnt][0] = g;
		numSwaps[cnt][1] = find_next(g);
		
		//printf("xxxx %d %d\n",g,find_next(g));
				
		swap(aux[numSwaps[cnt][0]] , aux[numSwaps[cnt][1]]);
		
		cnt++;
	}
	
	for(int g = 1 ; g <= n ; g++) aux[g] = S[g];
	
	for(int g = 1 ; g <= cnt ; g++)
	{
		//for(int h = 1 ; h <= n ; h++) printf("%d ",aux[h]);
		//printf("\n");
		
		swap(aux[X[g]] , aux[Y[g]]);
		
		int id[2];
		
		for(int h = 1 ; h <= n ; h++)
			for(int l = 0 ; l < 2 ; l++)
				if(aux[h] == numSwaps[g - 1][l]) id[l] = h;

		P[g - 1] = id[0] - 1;
		Q[g - 1] = id[1] - 1;
		
		swap(aux[id[0]] , aux[id[1]]);
	}
	
	for(; cnt < ans ; cnt++) P[cnt] = Q[cnt] = 0;
		
	return ans;
}

/*int main()
{
	scanf("%d %d",&n,&m);
	
	for(int g = 0 ; g < n ; g++) scanf("%d",&s[g]);
	
	for(int g = 0 ; g < m ; g++) scanf("%d %d",&x[g],&y[g]);
	
	int t = findSwapPairs(n, s , m , x , y , p , q);
	
	printf("%d\n",t);
	
	for(int g = 0 ; g < t ; g++) printf("%d %d\n",p[g],q[g]);
}*/

Compilation message (stderr)

sorting.cpp: In function 'int find_next(int)':
sorting.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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