Submission #260053

#	Time	Username	Problem	Language	Result	Execution time	Memory
260053		arnold518	Swap (BOI16_swap)	C++14	48 / 100	1093 ms	90784 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];

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) { return btoi(p)==btoi(q); }
bool operator < (const bitset<18> &p, const bitset<18> &q) { return btoi(p)<btoi(q); }
bool operator > (const bitset<18> &p, const bitset<18> &q) { return btoi(p)>btoi(q); }

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(itob(A[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(itob(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++) 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(itob(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) 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++)
	{
		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:66: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:66: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:68: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:69: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:77: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:77: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:79: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:80: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:90: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:90: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:92: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:98:20: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
      if(p1[i]==p2[i]) ret.push_back(p1[i]), flag=0;
                    ^
swap.cpp:30:6: note: candidate 1: bool operator==(const std::bitset<18>&, const std::bitset<18>&)
 bool operator == (const bitset<18> &p, const bitset<18> &q) { return btoi(p)==btoi(q); }
      ^~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:66:0,
                 from swap.cpp:1:
/usr/include/c++/7/bitset:1298:7: note: candidate 2: bool std::bitset<_Nb>::operator==(const std::bitset<_Nb>&) const [with long unsigned int _Nb = 18]
       operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
       ^~~~~~~~
swap.cpp:103: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:109:20: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
      if(q1[j]==q2[j]) ret.push_back(q1[j]), flag=0;
                    ^
swap.cpp:30:6: note: candidate 1: bool operator==(const std::bitset<18>&, const std::bitset<18>&)
 bool operator == (const bitset<18> &p, const bitset<18> &q) { return btoi(p)==btoi(q); }
      ^~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:66:0,
                 from swap.cpp:1:
/usr/include/c++/7/bitset:1298:7: note: candidate 2: bool std::bitset<_Nb>::operator==(const std::bitset<_Nb>&) const [with long unsigned int _Nb = 18]
       operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
       ^~~~~~~~
swap.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:122: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: 0 / 20
• Subtask 5: 0 / 32