oj.uz

Submission #401261

# Submission time Handle Problem Language Result Execution time Memory
401261 2021-05-09T17:37:46 Z kshitij_sodani Sorting (IOI15_sorting) C++14
100 / 100
 474 ms 22880 KB 
//#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 pos[200001];
//int ind5[200001];
//int cur3[200001];
bool check(int mid){
	for(int i=0;i<n;i++){
		cur[i]=it[i];
		pos[it[i]]=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(pos[cur[xx[i]]],pos[cur[yy[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;
	/*	for(int j=0;j<n;j++){
			pos[cur[j]]=j;
		}*/
		while(ss.size()){
			int j=ss.front();
			ss.pop();
			if(cur2[pos[j]]!=cur[pos[j]]){
				ind=pos[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;
				}
			}	*/
			ind2=cur4[cur[ind]];
			//cout<<ind<<",,,"<<ind2<<endl;
			
			swap(cur[ind2],cur[ind]);
			pp[i]=ind;
			qq[i]=ind2;		
			swap(pos[cur[pp[i]]],pos[cur[qq[i]]]);
 
		}
		/*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 2 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 2 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 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 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 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 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 2 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 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 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 1 ms 332 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 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 2 ms 644 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 588 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 308 ms 20752 KB Output is correct
16 Correct 408 ms 21028 KB Output is correct
17 Correct 447 ms 21940 KB Output is correct
18 Correct 164 ms 18240 KB Output is correct
19 Correct 312 ms 20140 KB Output is correct
20 Correct 353 ms 20620 KB Output is correct
21 Correct 335 ms 20920 KB Output is correct
22 Correct 307 ms 22256 KB Output is correct
23 Correct 335 ms 22564 KB Output is correct
24 Correct 448 ms 22332 KB Output is correct
25 Correct 459 ms 22104 KB Output is correct
26 Correct 328 ms 20672 KB Output is correct
27 Correct 294 ms 20100 KB Output is correct
28 Correct 434 ms 22048 KB Output is correct
29 Correct 420 ms 21680 KB Output is correct
30 Correct 237 ms 19416 KB Output is correct
31 Correct 429 ms 21980 KB Output is correct
32 Correct 345 ms 22004 KB Output is correct
33 Correct 474 ms 22292 KB Output is correct
34 Correct 391 ms 22328 KB Output is correct
35 Correct 315 ms 20048 KB Output is correct
36 Correct 126 ms 19204 KB Output is correct
37 Correct 461 ms 22880 KB Output is correct
38 Correct 443 ms 22088 KB Output is correct
39 Correct 444 ms 22164 KB Output is correct