제출 #693776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693776		amirhoseinfar1385	Swap (BOI16_swap)	C++17	100 / 100	250 ms	49768 KiB

swap

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>dp,mergy;
vector<int>all;
int n;

int calmina(int a,int b,int pi,int pii){
	int wi=upper_bound(mergy[pi].begin(),mergy[pi].end(),min(a,b))-mergy[pi].begin();
	int wii=upper_bound(mergy[pii].begin(),mergy[pii].end(),min(a,b))-mergy[pii].begin();
	if(dp[pi][wi]<dp[pii][wii]){
		if(b==min(a,b)){
			return dp[pi][wi];
		}
		else{
			int z=upper_bound(mergy[pii].begin(),mergy[pii].end(),b)-mergy[pii].begin();
			return dp[pii][z];
		}
	}	
	else{
		if(b==min(a,b)){
			return dp[pii][wii];
		}
		else{
			int z=upper_bound(mergy[pi].begin(),mergy[pi].end(),b)-mergy[pi].begin();
			return dp[pi][z];
		}
	}
}

vector<int>merge(vector<int>a,vector<int>b){
	int i=0,j=0;
	vector<int>ret;
	while(i<(int)a.size()&&j<(int)b.size()){
		if(a[i]<b[j]){
			ret.push_back(a[i]);
			i++;
		}
		else{
			ret.push_back(b[j]);
			j++;
		}
	}
	while(i<(int)a.size()){
		ret.push_back(a[i]);
		i++;
	}
	while(j<(int)b.size()){
		ret.push_back(b[j]);
		j++;
	}
	return ret;
}

void solve(int u){
	if(u==0){
		return ;
	}
	if(u*2>=n+1){
		dp[u]={u,u};
		mergy[u].push_back(all[u]);
		return solve(u-1);
	}
	if(u*2==n)
	{
		mergy[u]=merge(mergy[(u<<1)],{all[u]});
		dp[u].resize((int)mergy[u].size()+1);
		for(int j=0;j<(int)dp[u].size();j++){
			if(j==(int)dp[u].size()-1){
				dp[u][j]=dp[u*2][j-1];
			}
			else{
			//	cout<<u<<" "<<j<<" "<<mergy[u][j]<<" "<<all[u*2]<<"\n";
				if(mergy[u][j]-1<all[u*2]){
					dp[u][j]=u;
					continue;
				}
				int p=upper_bound(mergy[u*2].begin(),dp[u*2].end(),mergy[u][j]-1)-mergy[u*2].begin();
				dp[u][j]=dp[u*2][p];
			}
		}
		return solve(u-1);
	}
	mergy[u]=merge(mergy[(u<<1)],{all[u]});
	mergy[u]=merge(mergy[u],mergy[(u<<1)^1]);
	dp[u].resize((int)mergy[u].size()+1);
	for(int j=0;j<(int)dp[u].size();j++){
		if(j==(int)dp[u].size()-1){
			if(all[u*2]<all[u*2+1]){
				dp[u][j]=dp[u*2].back();
				continue;
			}
			dp[u][j]=calmina(max(all[u*2+1],all[u*2]),mergy[u].back()+2,u*2,u*2+1);
		}
		else{
			if(mergy[u][j]-1<all[u*2]&&mergy[u][j]-1<all[u*2+1]){
				dp[u][j]=u;
				continue;
			}
			if(all[u*2]<min(mergy[u][j]-1,all[u*2+1])){
				int p=upper_bound(mergy[u*2].begin(),mergy[u*2].end(),mergy[u][j]-1)-mergy[u*2].begin();
				dp[u][j]=dp[u*2][p];
				continue;
			}
			dp[u][j]=calmina(max(all[u*2],all[u*2+1]),mergy[u][j]-1,u*2,u*2+1);
		}
	}
	return solve(u-1);
}
vector<int>res;

void calres(int u){
	if(u>n){
		return ;
	}
	if(u*2>n){
		return calres(u+1);
	}
	if(u*2==n){
		if(all[u]<all[u*2]){
			return calres(u+1);
		}
		else{
			swap(all[u],all[u*2]);
			return calres(u+1);
		}
	}
	int p=upper_bound(mergy[u].begin(),mergy[u].end(),all[u])-mergy[u].begin();
	if(dp[u][p]==u){
		return calres(u+1);
	}
//	if(all[u*2]<all[u*2+1]&&all[u*2]<all[u]){
//		swap(all[u*2],all[u]);
//		return calres(u+1);
//	}
	int f=dp[u][p];
	bool ff=0;
	while(f>0){
		if(f==(u<<1)){
			ff=1;
			break;
		}
		f>>=1;
	}
	if(ff){
		swap(all[u],all[u*2]);
		if(all[u]>all[u*2+1]){
			swap(all[u],all[u*2+1]);
		}
		return calres(u+1);
	}
	swap(all[u],all[u*2+1]);
	return calres(u+1);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	res.resize(n+1);
	all.resize(n+1);
	mergy.resize(n+1);
	dp.resize(n+1);
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	solve(n);
	/*for(int i=1;i<=n;i++){
		for(auto x:dp[i]){
			cout<<x<<" ";
		}
		cout<<"\n";
	}
	cout<<"\n";*/
	calres(1);
	for(int i=1;i<=n;i++){
		cout<<all[i]<<" ";
	}
	cout<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32