oj.uz

Submission #99158

# Submission time Handle Problem Language Result Execution time Memory
99158 2019-03-01T00:36:04 Z Lawliet Sorting (IOI15_sorting) C++14
0 / 100
 85 ms 46652 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 43000 KB Output is correct
2 Correct 85 ms 46652 KB Output is correct
3 Correct 82 ms 44280 KB Output is correct
4 Incorrect 61 ms 46584 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 43000 KB Output is correct
2 Correct 85 ms 46652 KB Output is correct
3 Correct 82 ms 44280 KB Output is correct
4 Incorrect 61 ms 46584 KB Output isn't correct
5 Halted 0 ms 0 KB -