Submission #114767

#	Time	Username	Problem	Language	Result	Execution time	Memory
114767		arman_ferdous	Sorting (IOI15_sorting)	C++17	100 / 100	218 ms	28152 KiB

sorting

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

const int N = 6e5+100;
int n, ss[N], m, x[N], y[N], p[N], q[N];

int tmp[N];
int solve(int M) {
	for(int i = 0; i < n; i++)
		tmp[i] = ss[i];
	for(int i = 0; i < M; i++)
		swap(tmp[x[i]], tmp[y[i]]);

	int cnt = 0;
	for(int i = 0; i < n; ) {
		if(i == tmp[i]) { i++; continue; }
		p[cnt] = tmp[i];
		q[cnt] = tmp[tmp[i]];
		swap(tmp[i], tmp[tmp[i]]);
		cnt++;
	}
	if(cnt > M) return -1;
	while(cnt < M) {
		p[cnt] = 0;
		q[cnt] = 0;
		cnt++;
	}
	return cnt;
}

int pos[N];
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++)
		ss[i] = S[i];
	for(int i = 0; i < m; i++)
		x[i] = X[i], y[i] = Y[i];

	int lo = 0, hi = M, idx;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		int R = solve(mid);
		if(R == -1) lo = mid+1;
		else idx = mid, hi = mid-1;
	}
	for(int i = 0; i < n; i++)
		pos[S[i]] = i;
	int R = solve(idx);

	for(int i = 0; i < R; i++) {
		swap(pos[ss[x[i]]], pos[ss[y[i]]]);
		swap(ss[x[i]], ss[y[i]]);

		P[i] = pos[p[i]];
		Q[i] = pos[q[i]];

		swap(pos[p[i]], pos[q[i]]);
		swap(ss[P[i]], ss[Q[i]]);
	}
	return R;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:19: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int R = solve(idx);
                   ^

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