Submission #126085

#	Time	Username	Problem	Language	Result	Execution time	Memory
126085		baluteshih	Sorting (IOI15_sorting)	C++14	36 / 100	99 ms	632 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int tag[200005],seq[200005],pl[200005];

void swp(int x,int y)
{
	swap(pl[seq[x]],pl[seq[y]]),swap(seq[x],seq[y]);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    int l=0,r=M;
    while(l<r)
    {
    	int mid=(l+r)/2,flag=1;
    	for(int i=0;i<N;++i)
    		seq[i]=S[i],pl[S[i]]=i,tag[i]=0;
    	for(int i=0;i<mid;++i)
    		++tag[X[i]],++tag[Y[i]];
    	for(int i=0;i<mid;++i)
    	{
			--tag[X[i]],--tag[Y[i]];
			swp(X[i],Y[i]);
			int untag=-1;
			for(int j=0;j<N;++j)
				if(seq[j]!=j&&(!~untag||tag[j]<tag[untag]))
					untag=j;
			if(!~untag) P[i]=Q[i]=0;
			else
				P[i]=untag,Q[i]=pl[untag],swp(P[i],Q[i]);
		}
		for(int i=0;i<N&&flag;++i)
			if(seq[i]!=i) flag=0;
		if(flag) r=mid;
		else l=mid+1;
	}
	int mid=l;
	for(int i=0;i<N;++i)
		seq[i]=S[i],pl[S[i]]=i,tag[i]=0;
	for(int i=0;i<mid;++i)
		++tag[X[i]],++tag[Y[i]];
	for(int i=0;i<mid;++i)
	{
		--tag[X[i]],--tag[Y[i]];
		swp(X[i],Y[i]);
		int untag=-1;
		for(int j=0;j<N;++j)
			if(seq[j]!=j&&(!~untag||tag[j]<tag[untag]))
				untag=j;
		if(!~untag) P[i]=Q[i]=0;
		else
			P[i]=untag,Q[i]=pl[untag],swp(P[i],Q[i]);
	}
	return l;
}

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