제출 #138329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138329		Sorting	정렬하기 (IOI15_sorting)	C++14	100 / 100	272 ms	24388 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){
	//cout << "dfs_ans  " << u << endl;
	//cout << tmp[u] << endl; 

	used[u] = true;

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

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

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

		swap(tmp[u], tmp[tmp[u]]);

		//cout << "swap " << tmp[u] << " " << tmp[tmp[u]] << endl;

		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;
}

/*int _s[N], _x[N], _y[N], _p[N], _q[N];

int main(){
	cin >> n >> m;

	for(int i = 0; i < n; i++){
		cin >> _s[i];
	}

	for(int i = 0; i < m; i++){
		cin >> _x[i] >> _y[i];
	}

	int ans = findSwapPairs(n, _s, m, _x, _y, _p, _q);

	cout << ans << "\n";

	for(int i = 0; i < ans; i++){
		cout << _p[i] << " " << _q[i] << "\n";
	}

	return 0;
}*/
/*
5 6
1 2 3 4 0
0 0 
0 0
0 0
0 0
0 0
0 0
*/

컴파일 시 표준 에러 (stderr) 메시지

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

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