제출 #241854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241854		Nightlight	정렬하기 (IOI15_sorting)	C++14	20 / 100	5 ms	640 KiB

sorting

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

int N, M;
int pos[200005];
int S[200005], A[200005];
int X[600005], Y[600005];
int P[600005], Q[600005];
int pp;

void balance(int now) {
	while(pp <= now) swap(S[X[pp]], S[Y[pp]]), pp++;
	while(pp > now + 1) swap(S[X[pp - 1]], S[Y[pp - 1]]), pp--;
}

bool trysort(int limit) {
	int cnt = 0;
//	cout << limit << "\n";
	for(int i = 0; i < N; i++) {
		A[i] = S[i];
//		cout << A[i] << " ";
		pos[A[i]] = i;
	}
//	cout << "\n";
	for(int i = 0; i < N; i++) {
		if(A[i] != i) {
			P[cnt] = i, Q[cnt] = pos[i];
			cnt++;
			int b = A[i];
			swap(A[i], A[pos[i]]);
			pos[b] = pos[i];
			pos[i] = i;
//			for(int j = 0; j < N; j++) {
//				cout << A[j] << " ";
//			}
//			cout << "\n";
		}
	}
	for(int i = cnt; i < limit; i++) {
		P[i] = 0, Q[i] = 0;
	}
//	cout << cnt << "\n\n";
	return cnt <= limit;
}

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++) S[i] = s[i];
	for(int i = 1; i <= M; i++) X[i] = x[i - 1], Y[i] = y[i - 1];
	int l = 0, r = M, res = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		balance(mid);
		if(trysort(mid)) {
			res = mid;
			r = mid - 1;
		}else l = mid + 1;
	}
	trysort(res);
	for(int i = 0; i < res; i++) {
		p[i] = P[i], q[i] = Q[i];
	}
//	system("pause");
	return res;
}

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