Submission #401113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401113	2021-05-09T11:51:40 Z	kshitij_sodani	Sorting (IOI15_sorting)	C++14	74 / 100	1000 ms	19708 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 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]]);
		}
		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;
		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	460 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	336 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	460 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	336 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	13 ms	436 KB	Output is correct
11	Correct	14 ms	332 KB	Output is correct
12	Correct	14 ms	432 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	13 ms	332 KB	Output is correct
4	Correct	13 ms	332 KB	Output is correct
5	Correct	13 ms	424 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	460 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	336 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	13 ms	436 KB	Output is correct
11	Correct	14 ms	332 KB	Output is correct
12	Correct	14 ms	432 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	13 ms	332 KB	Output is correct
16	Correct	13 ms	332 KB	Output is correct
17	Correct	13 ms	424 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	200 ms	700 KB	Output is correct
22	Correct	201 ms	816 KB	Output is correct
23	Correct	200 ms	708 KB	Output is correct
24	Correct	211 ms	748 KB	Output is correct
25	Correct	195 ms	836 KB	Output is correct
26	Correct	176 ms	744 KB	Output is correct
27	Correct	204 ms	708 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	580 KB	Output is correct
2	Correct	331 ms	552 KB	Output is correct
3	Correct	314 ms	548 KB	Output is correct
4	Correct	106 ms	540 KB	Output is correct
5	Correct	117 ms	560 KB	Output is correct
6	Correct	132 ms	516 KB	Output is correct
7	Correct	243 ms	672 KB	Output is correct
8	Correct	317 ms	548 KB	Output is correct
9	Correct	332 ms	552 KB	Output is correct
10	Correct	326 ms	548 KB	Output is correct
11	Correct	307 ms	580 KB	Output is correct
12	Correct	229 ms	572 KB	Output is correct
13	Correct	323 ms	580 KB	Output is correct
14	Correct	106 ms	548 KB	Output is correct

Subtask #6

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	580 KB	Output is correct
2	Correct	331 ms	552 KB	Output is correct
3	Correct	314 ms	548 KB	Output is correct
4	Correct	106 ms	540 KB	Output is correct
5	Correct	117 ms	560 KB	Output is correct
6	Correct	132 ms	516 KB	Output is correct
7	Correct	243 ms	672 KB	Output is correct
8	Correct	317 ms	548 KB	Output is correct
9	Correct	332 ms	552 KB	Output is correct
10	Correct	326 ms	548 KB	Output is correct
11	Correct	307 ms	580 KB	Output is correct
12	Correct	229 ms	572 KB	Output is correct
13	Correct	323 ms	580 KB	Output is correct
14	Correct	106 ms	548 KB	Output is correct
15	Execution timed out	1050 ms	19708 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-