Submission #401125

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401125	2021-05-09T12:09:46 Z	kshitij_sodani	Sorting (IOI15_sorting)	C++14	74 / 100	1000 ms	12860 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 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.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	3 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	332 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	3 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	332 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	36 ms	588 KB	Output is correct
22	Correct	36 ms	656 KB	Output is correct
23	Correct	37 ms	644 KB	Output is correct
24	Correct	38 ms	608 KB	Output is correct
25	Correct	34 ms	588 KB	Output is correct
26	Correct	33 ms	588 KB	Output is correct
27	Correct	36 ms	648 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	488 KB	Output is correct
2	Correct	185 ms	460 KB	Output is correct
3	Correct	165 ms	500 KB	Output is correct
4	Correct	57 ms	460 KB	Output is correct
5	Correct	67 ms	632 KB	Output is correct
6	Correct	77 ms	496 KB	Output is correct
7	Correct	133 ms	460 KB	Output is correct
8	Correct	173 ms	488 KB	Output is correct
9	Correct	181 ms	504 KB	Output is correct
10	Correct	183 ms	500 KB	Output is correct
11	Correct	189 ms	460 KB	Output is correct
12	Correct	136 ms	580 KB	Output is correct
13	Correct	185 ms	504 KB	Output is correct
14	Correct	57 ms	500 KB	Output is correct

Subtask #6

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	488 KB	Output is correct
2	Correct	185 ms	460 KB	Output is correct
3	Correct	165 ms	500 KB	Output is correct
4	Correct	57 ms	460 KB	Output is correct
5	Correct	67 ms	632 KB	Output is correct
6	Correct	77 ms	496 KB	Output is correct
7	Correct	133 ms	460 KB	Output is correct
8	Correct	173 ms	488 KB	Output is correct
9	Correct	181 ms	504 KB	Output is correct
10	Correct	183 ms	500 KB	Output is correct
11	Correct	189 ms	460 KB	Output is correct
12	Correct	136 ms	580 KB	Output is correct
13	Correct	185 ms	504 KB	Output is correct
14	Correct	57 ms	500 KB	Output is correct
15	Execution timed out	1094 ms	12860 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-