oj.uz

Submission #401260

# Submission time Handle Problem Language Result Execution time Memory
401260 2021-05-09T17:37:28 Z kshitij_sodani Sorting (IOI15_sorting) C++14
100 / 100
 472 ms 31540 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 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 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 332 KB Output is correct
5 Correct 1 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 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 332 KB Output is correct
17 Correct 1 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 2 ms 588 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 464 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 4 ms 532 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 464 KB Output is correct
12 Correct 2 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 464 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 4 ms 532 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 464 KB Output is correct
12 Correct 2 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 314 ms 20672 KB Output is correct
16 Correct 376 ms 28988 KB Output is correct
17 Correct 456 ms 30472 KB Output is correct
18 Correct 169 ms 26228 KB Output is correct
19 Correct 313 ms 28764 KB Output is correct
20 Correct 336 ms 29540 KB Output is correct
21 Correct 328 ms 29584 KB Output is correct
22 Correct 297 ms 25672 KB Output is correct
23 Correct 329 ms 31332 KB Output is correct
24 Correct 461 ms 30812 KB Output is correct
25 Correct 455 ms 30488 KB Output is correct
26 Correct 320 ms 29484 KB Output is correct
27 Correct 303 ms 28768 KB Output is correct
28 Correct 435 ms 30776 KB Output is correct
29 Correct 423 ms 30300 KB Output is correct
30 Correct 254 ms 28088 KB Output is correct
31 Correct 432 ms 30704 KB Output is correct
32 Correct 354 ms 30364 KB Output is correct
33 Correct 458 ms 30860 KB Output is correct
34 Correct 394 ms 30780 KB Output is correct
35 Correct 335 ms 28520 KB Output is correct
36 Correct 137 ms 27920 KB Output is correct
37 Correct 470 ms 31540 KB Output is correct
38 Correct 472 ms 30536 KB Output is correct
39 Correct 452 ms 30668 KB Output is correct