Submission #17291

#	Time	Username	Problem	Language	Result	Execution time	Memory
17291		erdemkiraz	Sorting (IOI15_sorting)	C++98	100 / 100	632 ms	17800 KiB

sorting

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include "sorting.h"

const int N = 2e5 + 5;

int n, m;
int s[N], a[N], h[N], w[N], p[N];
ii XY[N];

void swp(int x, int y) {
	int X = a[x];
	int Y = a[y];
	swap(w[X], w[Y]);
	swap(a[x], a[y]);
}

bool f(int x, int P[], int Q[]) {
	for(int i = 0; i < n; i++) {
		p[i] = i;
	}
	for(int i = 0; i < x; i++) {
		swap(p[XY[i].first], p[XY[i].second]);
	}
	for(int i = 0; i < n; i++) {
		w[s[i]] = i;
		a[i] = s[p[i]];
	}
	memset(h, 0, sizeof(h));
	int res = n, sz = 0;
	vector < int > v;
	vector < ii > ans;
	for(int i = 0; i < n; i++) {
		if(!h[i]) {
			res--;
			int x = i;
			v.clear();
			do{
				v.push_back(x);
				h[x] = 1;
				x = a[x];
			}while(x != i);
			for(int it = (int) v.size() - 1; it >= 1; it--) {
				int x = v[0];
				int y = v[it];
				ans.push_back(ii(a[x], a[y]));
			}
		}
	}
	for(int i = 0; i < n; i++)
		a[i] = s[i];
	if(res <= x) {
		for(int it = 0; it < ans.size(); it++) {
			swp(XY[it].first, XY[it].second);
			P[sz] = w[ans[it].first];
			Q[sz] = w[ans[it].second];
			sz++;
			swp(w[ans[it].first], w[ans[it].second]);
		}
		while(sz < x) {
			P[sz] = 0;
			Q[sz] = 0;
			sz++;
		}
		return 1;
	}
	return 0;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
	for(int i = 0; i < n; i++)
		s[i] = S[i];
	for(int i = 0; i < m; i++) {
		XY[i] = ii(X[i], Y[i]);
	}
	int l = 0, r = n - 1;
	while(l < r) {
		int m = (l + r) >> 1;
		if(f(m, P, Q))
			r = m;
		else
			l = m + 1;
	}
	f(l, P, Q);
	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'bool f(int, int*, int*)':
sorting.cpp:46:8: warning: declaration of 'int x' shadows a parameter [-Wshadow]
    int x = i;
        ^
sorting.cpp:28:12: note: shadowed declaration is here
 bool f(int x, int P[], int Q[]) {
            ^
sorting.cpp:54:9: warning: declaration of 'x' shadows a previous local [-Wshadow]
     int x = v[0];
         ^
sorting.cpp:46:8: note: shadowed declaration is here
    int x = i;
        ^
sorting.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int it = 0; it < ans.size(); it++) {
                   ~~~^~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:80:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:15:11: note: shadowed declaration is here
 const int N = 2e5 + 5;
           ^
sorting.cpp:90:7: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   int m = (l + r) >> 1;
       ^
sorting.cpp:17:8: note: shadowed declaration is here
 int n, m;
        ^

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