제출 #20226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20226		newtonis	정렬하기 (IOI15_sorting)	C++98	0 / 100	5 ms	640 KiB

sorting

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000;
const int maxm = 600000;

int n, m;
int S[maxn] , X[maxm] , Y[maxm];
int Fx[maxm] , Fy[maxm];

bool valid(int w){ // can we solve if there are w moves?
	//copy
	int cp1[maxn]; //f(position) = value
	int cp2[maxn]; //f(position) = value
	for (int i = 0;i < n;i++){ 
		cp1[i] = S[i]; 
		cp2[i] = S[i]; // copy array
	} 
	for (int i = 0;i < w;i++){ 
		swap (cp1[X[i]] , cp1[Y[i]]);  //make all swaps
	} 
	int fp[maxn]; //f(value) = position
	int ap[maxn]; //f(value) = position
	for (int i = 0;i < n;i++){ 
		ap[cp2[i]] = i; //where the value x is at start
		fp[cp1[i]] = i; //where the value x is at end
	}
	int f[maxn]; //f(position) = position
	int fi[maxn]; //inverse f
	//where is actually the value that will be in x position at end
	for (int i = 0;i < n;i++){  //for each value
		f[ ap[i] ] = fp[i]; //ap[i] = start of i value //fp[i] = end of i value
	} //f[x]=y means that the value on index x must be set to y
	for (int i = 0;i < n;i++){
		fi[f[i]] = i;
	}
	int a = 0;
	for (int i = 0;i < w;i++){
		swap( cp2[X[i]] , cp2[Y[i]]); //update
		swap( f[X[i]] , f[Y[i]]);

		ap[ cp2[X[i]] ] = X[i];
		ap[ cp2[Y[i]] ] = Y[i];
		fi[f[X[i]]] = X[i];
		fi[f[Y[i]]] = Y[i];

		bool end = false;
		while (not end and a < n){ 
			//a = 

			int a1 = ap[a]; //the item with value a 
			int a2 = fi[a]; //the value that will finish in a position
			if (a1 != a2){
				swap( cp2[ a1 ] , cp2 [ a2 ]);

				ap[cp2[a1]] = a1;
				ap[cp2[a2]] = a2;

				Fx[i] = a1;
				Fy[i] = a2;
				end = true;
			}
			a ++;
		}
		if (not end){
			Fx[i] = 0;
			Fy[i] = 0;
		}
	}
	for (int i = 0;i < n;i++){
		if (cp2[i] != i){ return false;}
	}
	return true;
}
int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
	//freopen("input.in","r",stdin);
	//freopen("output.out","w+",stdout);
	// input //
	n = N;
	m = M;
	for (int i = 0;i < n;i++){
		S[i] = s[i];
		X[i] = x[i];
		Y[i] = y[i];
	}
	/*cin >> n;
	for (int i = 0;i < n;i++){
		cin >> S[i];
	}
	cin >> m;
	for (int i = 0;i < m;i++){
		cin >> X[i] >> Y[i];
	}*/
	// computing solution = binary search //
	int a = -1, b = m+1; //in how many turns is possible to sort sequence
	while (a + 1 != b){
		int h = (a+b)/2;
		//cout << a << ' ' << h <<  ' ' << b << '\n';
		if (valid(h)){ //try to make (a,b) as low as possible 
			b = h; //settle range
		}else{
			a = h; 
		}
	}
	// showing output //
	valid(b);
	//cout << b << '\n';
	for (int i = 0;i < b;i++){
		//cout << Fx[i] << ' ' << Fy[i] << '\n';
		P[i] = Fx[i];
		Q[i] = Fy[i];
	}
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:113:1: warning: no return statement in function returning non-void [-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