Submission #260054

#	Time	Username	Problem	Language	Result	Execution time	Memory
260054		arnold518	Swap (BOI16_swap)	C++14	0 / 100	11 ms	17536 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];
bitset<18> B[MAXN+10];
vector<int> V[MAXN+10];

vector<bool> vis[MAXN+10];
vector<vector<bitset<18>>> dp[MAXN+10];

bitset<18> itob(int x)
{
	bitset<18> ret;
	for(int i=0; i<18; i++) if(x&(1<<i)) ret[i]=1;
	return ret;
}

int btoi(bitset<18> x)
{
	int ret=0;
	for(int i=0; i<18; i++) if(x[i]) ret|=(1<<i);
	return ret;
}

bool operator < (const bitset<18> &p, const bitset<18> &q)
{
	for(int i=17; i>=0; i--)
	{
		if(p[i]==q[i]) continue;
		if(p[i]) return true;
		if(q[i]) return false;
	}
	return false;
}

bool operator > (const bitset<18> &p, const bitset<18> &q)
{
	for(int i=17; i>=0; i--)
	{
		if(p[i]==q[i]) continue;
		if(p[i]) return false;
		if(q[i]) return true;
	}
	return false;
}

vector<bitset<18>> &solve(int now, int pp)
{
	int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
	if(V[now][qq]!=pp) while(1);
	if(vis[now][qq]) return dp[now][qq];
	vis[now][qq]=1;
	vector<bitset<18>> &ret=dp[now][qq];

	if(now*2>N)
	{
		ret.push_back(itob(A[pp]));
		return ret;
	}
	if(now*2+1>N)
	{
		if(A[pp]>A[now*2])
		{
			ret.push_back(itob(A[now*2]));
			ret.push_back(itob(A[pp]));
		}
		else
		{
			ret.push_back(itob(A[pp]));
			ret.push_back(itob(A[now*2]));
		}
		return ret;
	}

	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		vector<bitset<18>> &p=solve(now*2, now*2), &q=solve(now*2+1, now*2+1);
		ret.push_back(B[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++) ret.push_back(p[i]);
			for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
		}
		return ret;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		vector<bitset<18>> &p=solve(now*2, pp), &q=solve(now*2+1, now*2+1);
		ret.push_back(B[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++) ret.push_back(p[i]);
			for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
		}
		return ret;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		vector<bitset<18>> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
		vector<bitset<18>> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
		ret.push_back(B[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) ret.push_back(p1[i]);
				if(flag==2) ret.push_back(p2[i]);
				if(flag==0)
				{
					if(p1[i]==p2[i]) ret.push_back(p1[i]), flag=0;
					if(p1[i]<p2[i]) ret.push_back(p1[i]), flag=1;
					if(p1[i]>p2[i]) ret.push_back(p2[i]), flag=2;
				}
			}
			for(int t=0; t<(1<<k) && j<q1.size(); t++, j++)
			{
				if(flag==1) ret.push_back(q1[j]);
				if(flag==2) ret.push_back(q2[j]);
				if(flag==0)
				{
					if(q1[j]==q2[j]) ret.push_back(q1[j]), flag=0;
					if(q1[j]<q2[j]) ret.push_back(q1[j]), flag=1;
					if(q1[j]>q2[j]) ret.push_back(q2[j]), flag=2;
				}
			}
		}
		return ret;
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
	for(int i=1; i<=N; i++) B[i]=itob(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);
		reverse(V[i].begin(), V[i].end());
		vis[i].resize(V[i].size());
		dp[i].resize(V[i].size());
	}

	vector<bitset<18>> ans=solve(1, 1);
	for(auto it : ans) printf("%d ", btoi(it));
}

Compilation message (stderr)

swap.cpp: In function 'std::vector<std::bitset<18> >& solve(int, int)':
swap.cpp:85: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:85: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:87:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
                             ~^~~~~~~~~
swap.cpp:88:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
                             ~^~~~~~~~~
swap.cpp:96: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:96: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:98:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
                             ~^~~~~~~~~
swap.cpp:99:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
                             ~^~~~~~~~~
swap.cpp:109: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:109: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:111: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:122: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:136:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:141: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: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32