Submission #138313

#	Time	Username	Problem	Language	Result	Execution time	Memory
138313		Sorting	Sorting (IOI15_sorting)	C++14	0 / 100	3 ms	504 KiB

sorting

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

int n, m;
int *s, *x, *y, *p, *q;
int tmp[N], tmp2[N], where[N];
bool used[N];

int timer = 0;

int dfs(int u){
	used[u] = true;

	int cnt = 1;

	if(!used[ tmp[u] ]){
		cnt += dfs(tmp[u]);
	}

	return cnt;
}

void make_swap(int l, int r){
	swap(tmp2[l], tmp2[r]);
	swap(where[ tmp2[l] ], where[ tmp2[r] ]);
}

void dfs_ans (int u){
	used[u] = true;

	if(!used[ tmp[u] ]){
		dfs(tmp[u]);

		make_swap(x[timer], y[timer]);

		p[timer] = where[tmp[u]];
		q[timer] = where[u];

		make_swap(p[timer], q[timer]);

		++timer;
	}
}

bool check(int mid){
	for(int i = 0; i < n; i++){
		tmp[i] = s[i]; 
		used[i] = false;
	}

	for(int i = 0; i < mid; i++){
		swap(tmp[ x[i] ], tmp[ y[i] ]);
	}

	int cnt = 0;

	for(int i = 0; i < n; i++){
		if(!used[i]){
			cnt += dfs(i) - 1;
		}
	}

	return (cnt <= mid);
}

void find_ans(int mid){
	for(int i = 0; i < n; i++){
		tmp[i] = s[i]; 
		tmp2[i] = s[i];
		where[s[i]] = i;
		used[i] = false;
	}

	for(int i = 0; i < mid; i++){
		swap(tmp[ x[i] ], tmp[ y[i] ]);
		//swap(where[ s[x[i]] ], where[ s[y[i]] ]);
	}

	int cnt = 0;

	for(int i = 0; i < n; i++){
		if(!used[i]){
			dfs_ans(i);
		}
	}

	while(timer < mid){
		p[timer] = 0;
		q[timer++] = 0;
	}
}

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 = 0, r = m;

	while(l != r){
		int mid = (l + r) >> 1;

		if(check(mid)){
			r = mid;
		}
		else{
			l = mid + 1;
		}
	}

	find_ans(l);

	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'void find_ans(int)':
sorting.cpp:82:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

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