Submission #48990

#	Time	Username	Problem	Language	Result	Execution time	Memory
48990		Namnamseo	Sorting (IOI15_sorting)	C++17	100 / 100	509 ms	12412 KiB

sorting

#include "sorting.h"
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> pp;

int *x;
int n;

int *ea, *eb;
int *oa, *ob;

int cur[200010];
int mp [200010];

void w(int a,int b){
    swap(cur[a], cur[b]);
    swap(mp[cur[a]], mp[cur[b]]);
}

bool possible(int t){
    for(int i=0; i<n; ++i) cur[i] = x[i], mp[x[i]]=i;
    for(int i=0; i<t; ++i){
        int a=ea[i], b=eb[i];
        w(a,b);
    }
    int ind=0;
    for(int i=0; i<n; ++i){
        if(mp[i]==i) continue;
        int a=i, b=mp[i];
        oa[ind]=cur[i]; ob[ind]=i; ++ind;
        w(a, b);
    }
    if(ind>t) return false;
    for(;ind<t;++ind) oa[ind]=ob[ind]=0;
    for(int i=0; i<n; ++i) cur[i] = x[i], mp[x[i]]=i;
    for(int i=0; i<t; ++i){
        int a=ea[i], b=eb[i];
        swap(cur[a], cur[b]); swap(mp[cur[a]], mp[cur[b]]);
        
        int p=oa[i], q=ob[i];
        oa[i]=mp[p]; ob[i]=mp[q];
        w(oa[i], ob[i]);
    }
    return true;
}

int findSwapPairs(int N, int x_[], int m, int EA[], int EB[], int p[], int q[]) {
	n=N;
	x=x_;
	ea=EA; eb=EB;
	oa=p;  ob=q;
	int l=0, r=m;
	if(possible(l)) return l;
	while(l+1<r){
		int mid=(l+r)/2;
		if(possible(mid)) r=mid;
		else l=mid;
	}
	possible(r);
	return r;
}

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