oj.uz

Submission #1018976

# Submission time Handle Problem Language Result Execution time Memory
1018976 2024-07-10T11:27:52 Z amirhoseinfar1385 Sorting (IOI15_sorting) C++17
100 / 100
 291 ms 37872 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int all[maxn],n,q,fake[maxn],vis[maxn],lnk[maxn];
pair<int,int>alltagh[maxn];
 
void khor(){
	for(int i=0;i<n;i++){
		cout<<fake[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<all[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<lnk[i]<<endl;
	}
	cout<<endl;
	cout<<endl;
}
 
vector<vector<int>> besaz(int ind){
	vector<vector<int>>ret;
	for(int i=0;i<n;i++){
		fake[i]=all[i];
		vis[i]=0;
	}
	for(int i=1;i<=ind;i++){
		swap(fake[alltagh[i].first],fake[alltagh[i].second]);
	}
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			ret.push_back({});
			int now=i;
			while(vis[now]==0){
//				cout<<now<<" "<<fake[now]<<endl;
				vis[now]=1;
				ret.back().push_back(fake[now]);
				now=fake[now];
			}
		}
	}
	return ret;
}
 
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;
    for(int i=0;i<n;i++){
    	all[i]=S[i];
    	lnk[all[i]]=i;
    }
    q=M;
    for(int i=1;i<=q;i++){
    	alltagh[i]=make_pair(X[i-1],Y[i-1]);
    }
    int low=-1,high=q,mid;
    while(high-low>1){
    	mid=(high+low)>>1;
    	vector<vector<int>>te=besaz(mid);
    	if(n-(int)te.size()<=mid){
    		high=mid;
    	}else{
    		low=mid;
    	}
    }
//    for(int i=0;i<=q;i++){
  //  	if(n-besaz(i).size()<=i){
    //		high=i;
    //		break;
    //	}
   // }
   	vector<vector<int>>ger=besaz(high);
   	int now=0;
   	for(int i=0;i<(int)ger.size();i++){
   		for(int j=1;j<(int)ger[i].size();j++){
   			P[now]=min(ger[i][j],ger[i][j-1]);
   			Q[now]=max(ger[i][j],ger[i][j-1]);
   			now++;
   		}
   	}
   	for(int i=now;i<q;i++){
   		P[i]=Q[i]=0;
   	}
   	for(int i=1;i<=high;i++){
   		swap(lnk[all[alltagh[i].first]],lnk[all[alltagh[i].second]]);
   		swap(all[alltagh[i].first],all[alltagh[i].second]);
   		P[i-1]=lnk[P[i-1]];
   		Q[i-1]=lnk[Q[i-1]];
   		swap(lnk[all[P[i-1]]],lnk[all[Q[i-1]]]);
   		swap(all[P[i-1]],all[Q[i-1]]);
   	}
	return high;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8536 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 8792 KB Output is correct
22 Correct 1 ms 8792 KB Output is correct
23 Correct 2 ms 8796 KB Output is correct
24 Correct 1 ms 8796 KB Output is correct
25 Correct 2 ms 8796 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 1 ms 8808 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 2 ms 8896 KB Output is correct
15 Correct 119 ms 26568 KB Output is correct
16 Correct 125 ms 24564 KB Output is correct
17 Correct 136 ms 28584 KB Output is correct
18 Correct 231 ms 37872 KB Output is correct
19 Correct 204 ms 33216 KB Output is correct
20 Correct 213 ms 37120 KB Output is correct
21 Correct 207 ms 37136 KB Output is correct
22 Correct 118 ms 28596 KB Output is correct
23 Correct 134 ms 30012 KB Output is correct
24 Correct 135 ms 28464 KB Output is correct
25 Correct 137 ms 29052 KB Output is correct
26 Correct 233 ms 36592 KB Output is correct
27 Correct 222 ms 35840 KB Output is correct
28 Correct 162 ms 29012 KB Output is correct
29 Correct 160 ms 29756 KB Output is correct
30 Correct 291 ms 33428 KB Output is correct
31 Correct 161 ms 30164 KB Output is correct
32 Correct 139 ms 23980 KB Output is correct
33 Correct 142 ms 27656 KB Output is correct
34 Correct 131 ms 27472 KB Output is correct
35 Correct 201 ms 31544 KB Output is correct
36 Correct 239 ms 36376 KB Output is correct
37 Correct 151 ms 29384 KB Output is correct
38 Correct 147 ms 28572 KB Output is correct
39 Correct 137 ms 30308 KB Output is correct