oj.uz

Submission #1090937

# Submission time Handle Problem Language Result Execution time Memory
1090937 2024-09-19T08:06:30 Z owoovo Sorting (IOI15_sorting) C++17
16 / 100
 2 ms 616 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(tarp[tar[x[1]]],tarp[tar[y[1]]]);
			swap(tar[x[1]],tar[y[1]]);
			swap(s[x[1]],s[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^=x[ans+1]^y[ans+1];
				if(now==x[ans+1]||now==y[ans+1])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]]);
				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;
		}
		if(ok==0){
			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(tarp[tar[x[1]]],tarp[tar[y[1]]]);
		swap(tar[x[1]],tar[y[1]]);
		swap(s[x[1]],s[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){
			//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^=x[ans+1]^y[ans+1];
			if(now==x[ans+1]||now==y[ans+1])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]]);
			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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 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 456 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 616 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 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 456 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 616 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -