제출 #221805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221805		patrikpavic2	정렬하기 (IOI15_sorting)	C++17	100 / 100	494 ms	33956 KiB

sorting

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  sorting
* score: 100.0
* date:  2019-06-23 09:06:27.945005
*/
#include "sorting.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue> 
#include <algorithm>

using namespace std;

const int N = 1e6 + 500;

int E[N], EE[N], P[N], Q[N], S[N], SSS[N], X[N], Y[N], n;
queue < int > q;

bool check(int m){
	for(int i = 0;i < n;i++) S[i] = SSS[i];
	for(int i = 0;i < n;i++) EE[i] = i, E[i] = i;
    for(int i = m - 1;i >= 0;i--) {
    	swap(E[EE[X[i]]], E[EE[Y[i]]]);
    	swap(EE[X[i]], EE[Y[i]]);
    }
    for(int i = 0;i < n;i++){
   		q.push(i);
    }
    for(int i = 0;i < m;i++){
    	swap(S[X[i]], S[Y[i]]);
       	swap(EE[X[i]], EE[Y[i]]);
    	swap(E[EE[X[i]]], E[EE[Y[i]]]);
    	if(X[i] != E[S[X[i]]]) q.push(X[i]);
    	if(Y[i] != E[S[Y[i]]]) q.push(Y[i]);
    	P[i] = 0, Q[i] = 0;
    	for(;!q.empty() && q.front() == E[S[q.front()]]; q.pop());
    	if(!q.empty()) P[i] = q.front(), Q[i] = E[S[q.front()]];
    	swap(S[P[i]], S[Q[i]]);
    }
    for(;!q.empty() && q.front() == E[S[q.front()]]; q.pop());
    return q.empty();
}

int findSwapPairs(int nn, int SS[], int M, int XX[], int YY[], int PP[], int QQ[]) {
	n = nn;
	for(int i = 0;i < M;i++) X[i] = XX[i], Y[i] = YY[i];
	for(int i = 0;i < n;i++) SSS[i] = SS[i];
	int ans = -1;
	for(int i = 20;i >= 0;i--){
		if(ans + (1 << i) <= M && !check(ans + (1 << i)))
			ans += (1 << i);
	}
	check(ans + 1);
	for(int i = 0;i <= ans;i++)  
		PP[i] = P[i], QQ[i] = Q[i];
	return ans + 1;
}

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