Submission #974073

#	Time	Username	Problem	Language	Result	Execution time	Memory
974073		PagodePaiva	Sorting (IOI15_sorting)	C++17	36 / 100	1 ms	604 KiB

sorting

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

using namespace std;

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

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:33:11: warning: declaration of 'int x' shadows a parameter [-Wshadow]
   33 |       int x = i;
      |           ^
sorting.cpp:6:47: note: shadowed declaration is here
    6 | int findSwapPairs(int n, int st[], int m, int x[], int y[], int p[], int q[]) {
      |                                           ~~~~^~~
sorting.cpp:53:9: warning: unused variable 'inv' [-Wunused-variable]
   53 |     int inv[n+1], invst[n+1];
      |         ^~~

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