oj.uz

답안 #503625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503625 2022-01-08T13:07:05 Z uncripted Xor Sort (eJOI20_xorsort) C++11
0 / 100
 1 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
int pas[40005][3];
pair<int,int> m[2000002][21];
int lpow[2000002];
int power[18];
int a[2000002];
int a1[2000002];
int n;
void pow2calc(int x){
	power[1]=1;
	for(int i=2; i<=x; i++){
		power[i]=power[i-1]*2;
	}
	int cur=1;
	int curi=1;
	for(int i=1; i<=n; i++){
	if(cur*2<=i){
		cur*=2;
		curi++;
		lpow[i]=curi;
	}else{
		lpow[i]=curi;
	}
	
	}
}
void maxcalc(int x){
	for(int i=1; i<=x; i++){
		for(int j=1; j<=n; j++){
			if(i==1){
				m[j][1].f=a[j];
				m[j][1].s=j;
				continue;
			}
			if(j+power[i-1]<=n){
			
				m[j][i].f=max(m[j][i-1].f, m[j+power[i-1]][i-1].f);
				if(m[j][i].f==m[j][i-1].f){
				m[j][i].s=m[j][i-1].s;	
				
				}else{
					m[j][i].s=m[j+power[i-1]][i-1].s;
				}
				
			}
		}
	}
}
int maxrange(int l, int r){
		int x=lpow[r-l+1];
		int maxx=max(m[l][x].f, m[r-power[x]+1][x].f);
		int index=-1;
			if(maxx==m[l][x].f){
			index=m[l][x].s;	
			
			}else{
				index=m[r-power[x]+1][x].s;
			}
		return index;
}
int main(){
	int s;
	
	cin>>n;
	cin>>s;

	int k=0;

	for(int i=1; i<=n; i++){
		cin>>a[i];
		a1[i]=a[i];
	}
	pow2calc(20);
	maxcalc(20);
	int lastsort=n;
	while(lastsort!=1){
		int maxi=maxrange(1, lastsort);
	//	cout<<maxi<<"maxi"<<endl;
		a[maxi]=INT_MIN;
		maxcalc(20);
		for(int i=1; i<=lastsort-1; i++ ){
			k++;
			pas[k][1]=i;
			pas[k][2]=i+1; 
			
			
		//	cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[i]<<"cri1"<<endl;
			a1[i]=a1[i]^a1[i+1];
			
		//	cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[i]<<"crine1"<<endl;
		}
		for(int i=maxi+1; i<=lastsort; i++){
			k++;
			pas[k][1]=i;
			pas[k][2]=i-1;
	//		cout<<a1[i]<<" "<<a1[i-1]<<" "<<a1[i]<<"cri2"<<endl;
			a1[i]=a1[i]^a1[i-1];
			
	//		cout<<a1[i]<<" "<<a1[i-1]<<" "<<a1[i]<<"crine2"<<endl;
		}
		for(int i=maxi-2; i>=1; i--){
			k++;
			pas[k][1]=i;
			pas[k][2]=i+1;
	//		cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[i]<<"cri3"<<endl;
			a1[i]=a1[i]^a1[i+1];
			
		//	cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[i]<<"crine3"<<endl;
			
		}
	//	cout<<a1[lastsort]<<" cr "<<endl;
		lastsort--;
	}
	for(int i=n-1; i>=1; i--){
		k++;
		pas[k][1]=i;
		pas[k][2]=i+1;
		a1[i]=a1[i]^a1[i+1];
	}


	cout<<k<<endl;
	for(int i=1; i<=k; i++){
		cout<<pas[i][1]<<" "<<pas[i][2]<<endl;
	}
	
	cout<<endl;
	for(int i=1; i<=n; i++){
	//	cout<<a1[i]<<" ";
	}
	

	
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Not sorted
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Not sorted
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Not sorted
3 Halted 0 ms 0 KB -