Submission #1215377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215377		boclobanchat	Swap (BOI16_swap)	C++20	0 / 100	1 ms	320 KiB

swap

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
long long A[MAXN];
bool ck[MAXN];
vector<int> solve(vector<int> vi)
{
	if(vi.size()==1) return vi;
	if(vi.size()==2)
	{
		if(vi[0]>vi[1]) swap(vi[0],vi[1]);
		return vi;
	}
	int sz=vi.size();
	vector<int> va,vb;
	for(int i=1;i<sz;i++) if(ck[i+1]) va.push_back(vi[i]);
	else vb.push_back(vi[i]);
	int a=vi[0],b=vi[1],c=vi[2];
	if(a>c&&b>c)
	{
		vb[0]=vi[0];
		vector<int> vx=solve(va),vy=solve(vb),ans1={c},ans2={c};
		int l=0,r=0;
		for(int i=1;i<sz;i++) if(ck[i+1]) ans1.push_back(vx[l++]);
		else ans1.push_back(vy[r++]);
		swap(va[0],vb[0]);
		va=solve(va),vb=solve(vb);
		l=0,r=0;
		for(int i=1;i<sz;i++) if(ck[i+1]) ans2.push_back(va[l++]);
		else ans2.push_back(vb[r++]);
		if(ans1<ans2) return ans1;
		return ans2;
	}
	else
	{
		vector<int> ans;
		if(a<b&&c<b) va[0]=vi[0],ans.push_back(vi[1]);
		else ans.push_back(vi[0]);
		va=solve(va),vb=solve(vb);
		int l=0,r=0;
		for(int i=1;i<sz;i++) if(ck[i+1]) ans.push_back(va[l++]);
		else ans.push_back(vb[r++]);
		return ans;
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int> vi;
    ck[2]=true;
    for(int i=3;i<=n;i++) ck[i]=ck[i/2];
    for(int i=1;i<=n;i++)
    {
    	int res;
    	cin>>res;
    	vi.push_back(res);
	}
	vector<int> ans=solve(vi);
	for(auto v:ans) cout<<v<<" ";
}

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