Submission #46336

#	Time	Username	Problem	Language	Result	Execution time	Memory
46336		jun6873	Sorting (IOI15_sorting)	C++11	100 / 100	634 ms	29464 KiB

sorting

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

typedef pair<int, int> pint;
#define x first
#define y second

int n, *s;
int m, *x, *y, *p, *q;

const int maxn = 200004;
bool vis[maxn];
int now[maxn], rev[maxn];
int dfs(int *nxt, vector<pint>& rec, int k) {
	if (vis[k]) return k; vis[k] = 1;
	int l = dfs(nxt, rec, nxt[k]);
	if (k!=l) rec.emplace_back(k, l);
	return l;
}

bool possible(int k) {
	copy(s, s+n, now);
	for (int i=0; i<k; i++) swap(now[x[i]], now[y[i]]);

	vector<pint> pr;
	memset(vis, 0, sizeof(vis));
	for (int i=0; i<n; i++) if (!vis[i]) dfs(now, pr, i);

	if (pr.size() > k) return false;

	iota(now, now+n, 0);
	iota(rev, rev+n, 0);
	for (int i=k-1; ~i; i--) {
		if (pr.size() <= i)	{
			p[i] = q[i] = 0;
		} else {
			p[i] = rev[pr[i].x];
			q[i] = rev[pr[i].y];
		}
		swap(rev[now[p[i]]], rev[now[q[i]]]); swap(now[p[i]], now[q[i]]);
		swap(rev[now[x[i]]], rev[now[y[i]]]); swap(now[x[i]], now[y[i]]);
	}

	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N; s = S; m = M; x = X; y = Y; p = P; q = Q;

	int l = -1, r = m+1;
	while (l+1<r) {
		int m = (l+r)/2;
		if (possible(m)) r = m;
		else l = m;
	}

	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int dfs(int*, std::vector<std::pair<int, int> >&, int)':
sorting.cpp:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (vis[k]) return k; vis[k] = 1;
  ^~
sorting.cpp:16:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (vis[k]) return k; vis[k] = 1;
                        ^~~
sorting.cpp: In function 'bool possible(int)':
sorting.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (pr.size() > k) return false;
      ~~~~~~~~~~^~~
sorting.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pr.size() <= i) {
       ~~~~~~~~~~^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:53:7: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   int m = (l+r)/2;
       ^
sorting.cpp:10:5: note: shadowed declaration is here
 int m, *x, *y, *p, *q;
     ^

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