Submission #973995

#	Time	Username	Problem	Language	Result	Execution time	Memory
973995		PagodePaiva	Sorting (IOI15_sorting)	C++17	20 / 100	7 ms	620 KiB

sorting

#include<bits/stdc++.h>
#include "sorting.h"

using namespace std;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int pai[n];
    for(int i = 0;i < n;i++){
    	pai[s[i]] = i;
    }
    bool aux = true;
    for(int i = 1;i < n;i++){
    	if(s[i] < s[i-1]) aux = false;
    }
    if(aux){
    	return 0;
    }
    int l = 0, r = m-1;
    int resp = -1;
    while(l <= r){
    	int mid = (l+r)>>1;
    	int paimid[n];
    	int mark[n];
    	for(int i = 0;i < n;i++) {
    		paimid[i] = pai[i];
    		mark[i] = false;
    	}
    	for(int i = l;i <= mid;i++){
    		swap(paimid[x[i]], paimid[y[i]]);
    	}
    	int res = 0;
    	for(int i = 0;i < n;i++){
    		if(mark[i]) continue;
    		int x = i;
    		while(!mark[x]){
    			res++;
    			mark[x] = true;
    			x = paimid[x];
    		}
    		res--;
    	}
    	if(res <= mid+1){
    		r = mid-1;
    		resp = mid;
    	}
    	else{
    		for(int i = 0;i < n;i++) pai[i] = paimid[i];
    		l = mid+1;
    	}
    }
    // cout << resp << '\n';
    for(int i = 0;i < m;i++) p[i] = q[i] = 0;
	vector <int> v;
	for(int i = 0;i < n;i++){
		v.push_back(i);
	}
	for(int i = resp;i >= 0;i--){
		swap(v[x[i]], v[y[i]]);
	}
	int at = 0;
	for(int i = 0;i <= resp;i++){
		bool aux = true;
		for(int j = 1;j < n;j++){
			if(s[j] < s[j-1]) aux = false;
		}
		if(aux) break;
		swap(v[x[i]], v[y[i]]);
		swap(s[x[i]], s[y[i]]);
		int poss, posv;
		while(true){
			if(at == n){
				p[i] = 0;
				q[i] = 0;
				return i+1;
			}
			for(int j = 0;j < n;j++){
				if(s[j] == at) poss = j;
				if(v[j] == at) posv = j;
			}
			if(poss == posv){
				at++;
				continue;
			}
			// cout << poss << ' ' << posv << '\n';
			p[i] = poss;
			q[i] = posv;
			at++;
			break;
		}
		swap(s[poss], s[posv]);
		if(at == n){
		// for(int j = 0;j <= i;j++) cout << p[j] << ' ' << q[j] << "\n";
			return i+1;
		}
		while(true){
			if(at == n){
				// for(int j = 0;j <= i;j++) cout << p[j] << ' ' << q[j] << "\n";
				return i+1;
			}
			int poss, posv;
			for(int j = 0;j < n;j++){
				if(s[j] == at) poss = j;
				if(v[j] == at) posv = j;
			}
			if(poss == posv){
				at++;
				continue;
			}
			break;
		}
	}
	// for(int j = 0;j <= resp;j++) cout << p[j] << ' ' << q[j] << "\n";
	return resp+1;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:34:11: warning: declaration of 'int x' shadows a parameter [-Wshadow]
   34 |       int x = i;
      |           ^
sorting.cpp:6:46: note: shadowed declaration is here
    6 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
      |                                          ~~~~^~~
sorting.cpp:62:8: warning: declaration of 'aux' shadows a previous local [-Wshadow]
   62 |   bool aux = true;
      |        ^~~
sorting.cpp:11:10: note: shadowed declaration is here
   11 |     bool aux = true;
      |          ^~~
sorting.cpp:100:8: warning: declaration of 'poss' shadows a previous local [-Wshadow]
  100 |    int poss, posv;
      |        ^~~~
sorting.cpp:69:7: note: shadowed declaration is here
   69 |   int poss, posv;
      |       ^~~~
sorting.cpp:100:14: warning: declaration of 'posv' shadows a previous local [-Wshadow]
  100 |    int poss, posv;
      |              ^~~~
sorting.cpp:69:13: note: shadowed declaration is here
   69 |   int poss, posv;
      |             ^~~~
sorting.cpp:105:4: warning: 'posv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |    if(poss == posv){
      |    ^~
sorting.cpp:105:4: warning: 'poss' may be used uninitialized in this function [-Wmaybe-uninitialized]
sorting.cpp:90:19: warning: 'posv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |   swap(s[poss], s[posv]);
      |                   ^~~~
sorting.cpp:90:10: warning: 'poss' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |   swap(s[poss], s[posv]);
      |          ^~~~

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