oj.uz

Submission #1090963

# Submission time Handle Problem Language Result Execution time Memory
1090963 2024-09-19T09:01:49 Z owoovo Sorting (IOI15_sorting) C++17
74 / 100
 198 ms 23760 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int tar[1000010],tarp[1000010],n,x[1000010],y[1000010],s[1000010];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N;
	for(int i=0;i<M;i++){
		x[i+1]=X[i];
		y[i+1]=Y[i];
	}
	int l=0,r=M;
	while(l!=r){
		int m=(l+r)>>1,ok=1;
		//cout<<l<<" "<<r<<" "<<m<<"\n";
		for(int i=0;i<N;i++){
			tar[i]=i;
			s[i]=S[i];
		}
		for(int i=m;i>0;i--){
			swap(tar[x[i]],tar[y[i]]);
		}
		for(int i=0;i<N;i++){
			tarp[tar[i]]=i;
		}
		int ans=0;
		for(int i=0;i<N;i++){
			if(s[i]==tar[i])continue;
			int ori=i;
			while(tarp[s[ori]]!=ori){
				P[ans]=tarp[s[ori]];
				Q[ans]=ori;
				swap(s[tarp[s[ori]]],s[ori]);
				ans++;
				if(ans>=m)break;
			}
			if(ans>=m)break;
		}
		for(int i=0;i<N;i++){
			//cout<<s[i]<<" "<<tar[i]<<"\n";
			if(s[i]!=tar[i])ok=0;
		}
		//cout<<ok<<"\n";
		if(ok==0||ans>m){
			l=m+1;
		}else{
			r=m;
		}
	}

	int m=l;
	for(int i=0;i<N;i++){
		tar[i]=i;
		s[i]=S[i];
	}
	for(int i=m;i>0;i--){
		swap(tar[x[i]],tar[y[i]]);
	}
	for(int i=0;i<N;i++){	
		tarp[tar[i]]=i;
	}
	if(m!=0){
		swap(tar[x[1]],tar[y[1]]);
		swap(s[x[1]],s[y[1]]);
		tarp[tar[x[1]]]=x[1];
		tarp[tar[y[1]]]=y[1];
	}
	int ans=0;
	for(int i=0;i<N;i++){
		//cout<<s[i]<<" "<<tar[i]<<"\n";
		if(s[i]==tar[i])continue;
		int ori=i;
		while(ori!=tarp[s[ori]]){
			//cout<<now<<" "<<ori<<"\n";
			P[ans]=tarp[s[ori]];
			Q[ans]=ori;
			swap(s[tarp[s[ori]]],s[ori]);
			ans++;
			if(ans>=m)break;
			if(ori==x[ans+1])ori=y[ans+1];
			else if(ori==y[ans+1])ori=x[ans+1];
			swap(tar[x[ans+1]],tar[y[ans+1]]);
			swap(s[x[ans+1]],s[y[ans+1]]);
			tarp[tar[x[ans+1]]]=x[ans+1];
			tarp[tar[y[ans+1]]]=y[ans+1];
		}
		if(ans>=m)break;
	}
	for(int i=ans;i<m;i++)Q[i]=0,P[i]=0;
	return l;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 444 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 652 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 672 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 456 KB Output is correct
15 Correct 174 ms 21588 KB Output is correct
16 Correct 183 ms 22000 KB Output is correct
17 Correct 198 ms 23016 KB Output is correct
18 Correct 68 ms 20564 KB Output is correct
19 Correct 134 ms 22984 KB Output is correct
20 Correct 137 ms 23512 KB Output is correct
21 Correct 137 ms 23636 KB Output is correct
22 Correct 164 ms 19028 KB Output is correct
23 Correct 198 ms 23760 KB Output is correct
24 Correct 198 ms 23400 KB Output is correct
25 Correct 188 ms 23248 KB Output is correct
26 Incorrect 126 ms 22752 KB Output isn't correct
27 Halted 0 ms 0 KB -