Submission #401126

#	Time	Username	Problem	Language	Result	Execution time	Memory
401126		kshitij_sodani	Sorting (IOI15_sorting)	C++14	74 / 100	1086 ms	13188 KiB

sorting

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
 
#include "sorting.h"
//int cur[200001];
int it[200001];
int n;
int xx[3*200001];
int yy[3*200001];
int pp[3*200001];
int qq[3*200001];
int cur[200001];//position in which it  has to end up
int cur2[200001];//position in which number is currently ends in
//int cur3[2000001];//position which indes up in 
int cur4[200001];
//int ind5[200001];
//int cur3[200001];
bool check(int mid){
	for(int i=0;i<n;i++){
		cur[i]=it[i];
	}
/*	for(int i=0;i<n;i++){
		cout<<cur[i]<<"<";
	}
	cout<<endl;*/
	//cout<<mid<<",,"<<endl;
	for(int ii=0;ii<n;ii++){
			cur4[ii]=ii;
			//ind5[ii]=i;
		}
		for(int j=0;j<mid;j++){

			swap(cur4[xx[j]],cur4[yy[j]]);
		}

		queue<int> ss;
		for(int i=0;i<n;i++){
			ss.push(i);
		}
		for(int j=0;j<n;j++){
			cur2[cur4[j]]=j;
		}
	for(int i=0;i<mid;i++){
		swap(cur[xx[i]],cur[yy[i]]);
		/*for(int ii=0;ii<n;ii++){
			cout<<cur[ii]<<"/";
		}*/
		//cout<<endl;
		//cout<<xx[i]<<"<<"<<yy[i]<<endl;
		/*for(int j=0;j<n;j++){
			cout<<cur[j]<<",";
		}
		cout<<endl;
*/		
		/*for(int ii=0;ii<n;ii++){
			cur4[ii]=ii;
		}
		for(int j=i+1;j<mid;j++){
			swap(cur4[xx[j]],cur4[yy[j]]);
		}*/
		pair<int,int> cur3;
		cur3.a=cur2[xx[i]];
		cur3.b=cur2[yy[i]];
		/*for(int j=0;j<n;j++){
			if(cur4[j]==xx[i]){
				cur3.a=j;
			}
			if(cur4[j]==yy[i]){
				cur3.b=j;
			}

		}*/
		swap(cur4[cur3.a],cur4[cur3.b]);
		swap(cur2[xx[i]],cur2[yy[i]]);
		/*for(int j=0;j<n;j++){
			cur2[cur4[j]]=j;
		}*/
		/*for(int j=0;j<n;j++){
			cout<<cur2[j]<<":";
		}
		cout<<endl;*/
		int ind=-1;
		/*while(ss.size()){
			int no=ss.front();
			ss.pop();
			if(cur2[j]!=cur[j]){
				ind=j;
				break;
			}

		}*/
		for(int j=0;j<n;j++){
			if(cur2[j]!=cur[j]){
				ind=j;
				break;
			}
		}
		//cout<<ind<<":"<<endl;
		if(ind==-1){
			pp[i]=0;
			qq[i]=0;
		}
		else{
			int ind2=-1;
			for(int j=0;j<n;j++){
				if(cur2[j]==cur[ind]){
					ind2=j;
					break;
				}
			}	
			//cout<<ind<<",,,"<<ind2<<endl;
			swap(cur[ind2],cur[ind]);
			pp[i]=ind;
			qq[i]=ind2;		
 
		}
		/*for(int j=0;j<n;j++){
			cout<<cur[j]<<",";
		}
		cout<<endl;
 */
		/*for(int j=0;j<mid;j++){
 
		}*/
 
	}
	for(int i=0;i<n;i++){
		if(cur[i]!=i){
			return false;
		}
	}
/*	for(int i=0;i<n;i++){
		cout<<cur[i]<<"<";
	}
	cout<<endl;*/
	return true;
}
int findSwapPairs(int nn, int aa[], int m, int x[], int y[], int p[], int q[]){
	n=nn;
	for(int i=0;i<n;i++){
		it[i]=aa[i];
		//cout<<it[i]<<",";
	}
	//cout<<endl;
 
	for(int i=0;i<m;i++){
		xx[i]=x[i];
		yy[i]=y[i];
	}
	int low=-1;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=m){
			if(check(low+(1<<j))==false){
				low+=(1<<j);
			}
		}
 
	}
	low+=1;
	//cout<<low<<":"<<endl;
	check(low);
	for(int i=0;i<low;i++){
		p[i]=pp[i];
		q[i]=qq[i];
	}
	return low;
}

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