Submission #401121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401121	2021-05-09T12:08:04 Z	kshitij_sodani	Sorting (IOI15_sorting)	C++14	74 / 100	1000 ms	12852 KB

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 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;
		}
		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 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;
		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]);
		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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	3 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	3 ms	332 KB	Output is correct
4	Correct	3 ms	336 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct

Subtask #4

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	4 ms	332 KB	Output is correct
11	Correct	3 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	3 ms	332 KB	Output is correct
16	Correct	3 ms	336 KB	Output is correct
17	Correct	3 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	48 ms	648 KB	Output is correct
22	Correct	46 ms	708 KB	Output is correct
23	Correct	53 ms	640 KB	Output is correct
24	Correct	50 ms	640 KB	Output is correct
25	Correct	41 ms	616 KB	Output is correct
26	Correct	42 ms	648 KB	Output is correct
27	Correct	45 ms	636 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	476 KB	Output is correct
2	Correct	240 ms	496 KB	Output is correct
3	Correct	221 ms	500 KB	Output is correct
4	Correct	76 ms	504 KB	Output is correct
5	Correct	85 ms	624 KB	Output is correct
6	Correct	98 ms	492 KB	Output is correct
7	Correct	178 ms	520 KB	Output is correct
8	Correct	242 ms	620 KB	Output is correct
9	Correct	234 ms	508 KB	Output is correct
10	Correct	243 ms	460 KB	Output is correct
11	Correct	238 ms	512 KB	Output is correct
12	Correct	172 ms	532 KB	Output is correct
13	Correct	240 ms	580 KB	Output is correct
14	Correct	73 ms	500 KB	Output is correct

Subtask #6

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	476 KB	Output is correct
2	Correct	240 ms	496 KB	Output is correct
3	Correct	221 ms	500 KB	Output is correct
4	Correct	76 ms	504 KB	Output is correct
5	Correct	85 ms	624 KB	Output is correct
6	Correct	98 ms	492 KB	Output is correct
7	Correct	178 ms	520 KB	Output is correct
8	Correct	242 ms	620 KB	Output is correct
9	Correct	234 ms	508 KB	Output is correct
10	Correct	243 ms	460 KB	Output is correct
11	Correct	238 ms	512 KB	Output is correct
12	Correct	172 ms	532 KB	Output is correct
13	Correct	240 ms	580 KB	Output is correct
14	Correct	73 ms	500 KB	Output is correct
15	Execution timed out	1097 ms	12852 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-