oj.uz

Submission #1090949

# Submission time Handle Problem Language Result Execution time Memory
1090949 2024-09-19T08:41:15 Z owoovo Sorting (IOI15_sorting) C++17
54 / 100
 1 ms 636 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int tar[200010],tarp[200010],n,x[200010],y[200010],s[200010];

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;
		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];
		}
		for(int i=0;i<N;i++){
			if(s[i]==tar[i])continue;
			int now=tarp[s[i]],ori=i;
			while(now!=ori){
				P[ans]=now;
				Q[ans]=ori;
				swap(s[now],s[ori]);
				ans++;
				if(ans>=m)break;
				if(ori==x[ans+1]||ori==y[ans+1])ori=ori^x[ans+1]^y[ans+1];
				if(now==x[ans+1]||now==y[ans+1])now=now^x[ans+1]^y[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];
				now=tarp[s[ori]];
			}
			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;
	}
	int ans=0;
	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];
	}
	for(int i=0;i<N;i++){
		//cout<<s[i]<<" "<<tar[i]<<"\n";
		if(s[i]==tar[i])continue;
		int now=tarp[s[i]],ori=i;
		while(now!=ori){
			//cout<<now<<" "<<ori<<"\n";
			P[ans]=now;
			Q[ans]=ori;
			swap(s[now],s[ori]);
			ans++;
			if(ans>=m)break;
			if(ori==x[ans+1]||ori==y[ans+1])ori=ori^x[ans+1]^y[ans+1];
			if(now==x[ans+1]||now==y[ans+1])now=now^x[ans+1]^y[ans+1];
			swap(tarp[tar[x[ans+1]]],tarp[tar[y[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];
			now=tarp[s[ori]];
		}
		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 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 448 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 0 ms 348 KB Output is correct
2 Correct 0 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 448 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 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 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 604 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 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 612 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 1 ms 608 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 612 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 1 ms 608 KB Output isn't correct
12 Halted 0 ms 0 KB -