oj.uz

Submission #693776

# Submission time Handle Problem Language Result Execution time Memory
693776 2023-02-03T08:17:34 Z amirhoseinfar1385 Swap (BOI16_swap) C++17
100 / 100
 250 ms 49768 KB 
#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.0 / 10.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 452 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 66 ms 12220 KB Output is correct
17 Correct 55 ms 12192 KB Output is correct
18 Correct 56 ms 12188 KB Output is correct
19 Correct 32 ms 12224 KB Output is correct
20 Correct 28 ms 12228 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 66 ms 12220 KB Output is correct
17 Correct 55 ms 12192 KB Output is correct
18 Correct 56 ms 12188 KB Output is correct
19 Correct 32 ms 12224 KB Output is correct
20 Correct 28 ms 12228 KB Output is correct
21 Correct 250 ms 49640 KB Output is correct
22 Correct 219 ms 49688 KB Output is correct
23 Correct 228 ms 49768 KB Output is correct
24 Correct 126 ms 49700 KB Output is correct
25 Correct 161 ms 49628 KB Output is correct