Submission #785328

#	Time	Username	Problem	Language	Result	Execution time	Memory
785328		NothingXD	정렬하기 (IOI15_sorting)	C++17	100 / 100	158 ms	17076 KiB

sorting

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << " ";
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, a[maxn], b[maxn], idx[maxn], x[3*maxn], y[3*maxn];
bool vis[maxn];

bool check(int k){
	for (int i = 0; i < n; i++) b[i] = a[i];
	for (int i = 0; i < k; i++){
		swap(b[x[i]], b[y[i]]);
	}
	memset(vis, false, sizeof vis);
	int cnt = 0;
	for (int i = 0; i < n; i++){
		if (!vis[i]) cnt++;
		int x = i;
		while(!vis[x]){
			vis[x] = true;
			x = b[x];
		}
	}
	return n - cnt <= k;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {

	n = N;
	for (int i = 0; i < n; i++){
		a[i] = S[i];
		idx[a[i]] = i;
	}
	for (int i = 0; i < M; i++){
		x[i] = X[i];
		y[i] = Y[i];
	}
	int l = -1, r = M;
	while(l + 1 < r){
		int mid = (l+r) >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}

	for (int i = 0; i < n; i++){
		b[i] = a[i];
	}
	for (int i = 0; i < r; i++){
		swap(b[x[i]], b[y[i]]);
	}

	vector<pii> swp;
	memset(vis, false, sizeof vis);
	for (int i = 0; i < n; i++){
		int x = i;
		vector<int> ver;
		while(!vis[x]){
			ver.push_back(x);
			vis[x] = true;
			x = b[x];
		}
		for (int j = 1; j < ver.size(); j++){
			swp.push_back(MP(ver[j-1], ver[j]));
		}
	}

	for (int i = 0; i < r; i++){
		swap(a[x[i]], a[y[i]]);
		swap(idx[a[x[i]]], idx[a[y[i]]]);
		if (i < swp.size()){
			P[i] = idx[swp[i].F];
			Q[i] = idx[swp[i].S];
		}
		else{
			P[i] = Q[i] = 0;
		}
		swap(a[P[i]], a[Q[i]]);
		swap(idx[a[P[i]]], idx[a[Q[i]]]);
	}

	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'bool check(int)':
sorting.cpp:40:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   40 |   int x = i;
      |       ^
sorting.cpp:28:37: note: shadowed declaration is here
   28 | int n, a[maxn], b[maxn], idx[maxn], x[3*maxn], y[3*maxn];
      |                                     ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:77:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   77 |   int x = i;
      |       ^
sorting.cpp:28:37: note: shadowed declaration is here
   28 | int n, a[maxn], b[maxn], idx[maxn], x[3*maxn], y[3*maxn];
      |                                     ^
sorting.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int j = 1; j < ver.size(); j++){
      |                   ~~^~~~~~~~~~~~
sorting.cpp:92:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   if (i < swp.size()){
      |       ~~^~~~~~~~~~~~

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