Submission #260064

#	Time	Username	Problem	Language	Result	Execution time	Memory
260064		arnold518	Swap (BOI16_swap)	C++14	68 / 100	1104 ms	241520 KiB

swap

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
 
int N, A[MAXN+10];
vector<int> V[MAXN+10], D[MAXN+10];

vector<vector<int>> dp[MAXN+10];
 
int get(int now, int pp)
{
	return lower_bound(V[now].begin(), V[now].end(), pp, greater<int>())-V[now].begin();
}

void solve(int now, int pp)
{
	if(now*2>N)
	{
		dp[now][pp].push_back(A[V[now][pp]]);
		return;
	}
	if(now*2+1>N)
	{
		if(A[V[now][pp]]>A[now*2])
		{
			dp[now][pp].push_back(A[now*2]);
			dp[now][pp].push_back(A[V[now][pp]]);
		}
		else
		{
			dp[now][pp].push_back(A[V[now][pp]]);
			dp[now][pp].push_back(A[now*2]);
		}
		return;
	}
 
	if(A[V[now][pp]]<A[now*2] && A[V[now][pp]]<A[now*2+1])
	{
		vector<int> &p=dp[now*2][0], &q=dp[now*2+1][0];
		dp[now][pp].push_back(A[V[now][pp]]);
		for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p.size(); t++, i++) dp[now][pp].push_back(p[i]);
			for(int t=0; t<(1<<k) && j<q.size(); t++, j++) dp[now][pp].push_back(q[j]);
		}
		return;
	}
	if(A[now*2]<A[V[now][pp]] && A[now*2]<A[now*2+1])
	{
		vector<int> &p=dp[now*2][get(now*2, V[now][pp])], &q=dp[now*2+1][0];
		dp[now][pp].push_back(A[now*2]);
		for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p.size(); t++, i++) dp[now][pp].push_back(p[i]);
			for(int t=0; t<(1<<k) && j<q.size(); t++, j++) dp[now][pp].push_back(q[j]);
		}
		return;
	}
	if(A[now*2+1]<A[V[now][pp]] && A[now*2+1]<A[now*2])
	{
		vector<int> &p1=dp[now*2][get(now*2, V[now][pp])], &q1=dp[now*2+1][1];
		vector<int> &p2=dp[now*2][0], &q2=dp[now*2+1][get(now*2+1, V[now][pp])];
		dp[now][pp].push_back(A[now*2+1]);
		int flag=0;
		for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p1.size(); t++, i++)
			{
				if(flag==1) dp[now][pp].push_back(p1[i]);
				if(flag==2) dp[now][pp].push_back(p2[i]);
				if(flag==0)
				{
					if(p1[i]==p2[i]) dp[now][pp].push_back(p1[i]), flag=0;
					if(p1[i]<p2[i]) dp[now][pp].push_back(p1[i]), flag=1;
					if(p1[i]>p2[i]) dp[now][pp].push_back(p2[i]), flag=2;
				}
			}
			for(int t=0; t<(1<<k) && j<q1.size(); t++, j++)
			{
				if(flag==1) dp[now][pp].push_back(q1[j]);
				if(flag==2) dp[now][pp].push_back(q2[j]);
				if(flag==0)
				{
					if(q1[j]==q2[j]) dp[now][pp].push_back(q1[j]), flag=0;
					if(q1[j]<q2[j]) dp[now][pp].push_back(q1[j]), flag=1;
					if(q1[j]>q2[j]) dp[now][pp].push_back(q2[j]), flag=2;
				}
			}
		}
		return;
	}
}
 
int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
 
	for(int i=1; i<=N; i++)
	{
		int now=i;
		while(now!=1)
		{
			V[i].push_back(now);
			if(now%2) V[i].push_back(now-1);
			now/=2;
		}
		V[i].push_back(1);
		dp[i].resize(V[i].size());
	}

	int p=0;
	for(int i=1; i<=N; i++)
	{
		if(__builtin_popcount(i)==1) p++;
		D[p].push_back(i);
	}

	for(int now=N, p=N; now>=1; now--)
	{
		for(; p>now*2+1; p--)
		{
			for(auto &it : dp[p])
			{
				it.clear();
				it.shrink_to_fit();
			}
			dp[p].clear();
			dp[p].shrink_to_fit();
		}
		for(int pp=0; pp<V[now].size(); pp++)
		{
			solve(now, pp);
		}
	}

	for(auto it : dp[1][0]) printf("%d ", it);
}

Compilation message (stderr)

swap.cpp: In function 'void solve(int, int)':
swap.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                          ~^~~~~~~~~
swap.cpp:47:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                                        ~^~~~~~~~~
swap.cpp:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p.size(); t++, i++) dp[now][pp].push_back(p[i]);
                             ~^~~~~~~~~
swap.cpp:50:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q.size(); t++, j++) dp[now][pp].push_back(q[j]);
                             ~^~~~~~~~~
swap.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                          ~^~~~~~~~~
swap.cpp:58:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                                        ~^~~~~~~~~
swap.cpp:60:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p.size(); t++, i++) dp[now][pp].push_back(p[i]);
                             ~^~~~~~~~~
swap.cpp:61:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q.size(); t++, j++) dp[now][pp].push_back(q[j]);
                             ~^~~~~~~~~
swap.cpp:71:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
                          ~^~~~~~~~~~
swap.cpp:71:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
                                         ~^~~~~~~~~~
swap.cpp:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p1.size(); t++, i++)
                             ~^~~~~~~~~~
swap.cpp:84:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q1.size(); t++, j++)
                             ~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:137:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int pp=0; pp<V[now].size(); pp++)
                 ~~^~~~~~~~~~~~~~
swap.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:103:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
                          ~~~~~^~~~~~~~~~~~~

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