Submission #260285

#	Time	Username	Problem	Language	Result	Execution time	Memory
260285		arnold518	Swap (BOI16_swap)	C++14	100 / 100	465 ms	109900 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], C[MAXN+10];
 
int dep[MAXN+10];
bool vis[MAXN+10][36];
int dp[MAXN+10][36], memo[MAXN+10][36], ans[MAXN+10];
 
int solve(int now, int pp)
{
	int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
	if(vis[now][qq]) return dp[now][qq];
	vis[now][qq]=1;
	int &ret=dp[now][qq];
	int &mem=memo[now][qq];
 
	if(now*2>N)
	{
		ret=now;
		return ret;
	}
	if(now*2+1>N)
	{
		if(A[pp]>A[now*2]) ret=now*2;
		else ret=now;
		return ret;
	}
 
	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		ret=now;
		return ret;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		ret=solve(now*2, pp);
		return ret;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		int p1=solve(now*2, pp), q1=solve(now*2+1, now*2);
		int p2=solve(now*2, now*2), q2=solve(now*2+1, pp);
		if(A[pp]<A[now*2]) assert(p1<=p2);
		if(A[pp]>A[now*2]) assert(p1>=p2);
		if(A[now*2]<A[pp]) assert(q1<=q2);
		if(A[now*2]>A[pp]) assert(q1>=q2);
 
		int flag;
		if(min(dep[p1], dep[p2])<=min(dep[q1], dep[q2]))
		{
			if(p1==p2)
			{
				if(A[pp]<A[now*2]) flag=1;
				else flag=2;
			}
			if(p1<p2) flag=1;
			if(p1>p2) flag=2;
		}
		else
		{
			if(q1==q2)
			{
				if(A[now*2]<A[pp]) flag=1;
				else flag=2;
			}
			if(q1<q2) flag=1;
			if(q1>q2) flag=2;
		}
		mem=flag;
		if(flag==1) ret=p1;
		else ret=q2;
		return ret;
	}
}
 
void restore(int now, int pp)
{
	int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
	solve(now, pp);
	int mem=memo[now][qq];
	if(now*2>N)
	{
 		ans[now]=A[pp];
		return;
	}
	if(now*2+1>N)
	{
		if(A[pp]<A[now*2]) ans[now]=A[pp], ans[now*2]=A[now*2];
		else ans[now]=A[now*2], ans[now*2]=A[pp];
		return;
	}
 
	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		ans[now]=A[pp];
		restore(now*2, now*2);
		restore(now*2+1, now*2+1);
		return;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		ans[now]=A[now*2];
		restore(now*2, pp);
		restore(now*2+1, now*2+1);
		return;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		assert(mem==1 || mem==2);
		ans[now]=A[now*2+1];
		if(mem==1) { restore(now*2, pp); restore(now*2+1, now*2); }
		else { restore(now*2, now*2); restore(now*2+1, pp); }
	}
}
 
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; dep[i]=1;
		while(now!=1)
		{
			dep[i]++;
			V[i].push_back(now);
			C[now].push_back(i);
			if(now%2) V[i].push_back(now-1);
			now/=2;
		}
		C[1].push_back(i);
		V[i].push_back(1);
		reverse(V[i].begin(), V[i].end());
	}
	 
	restore(1, 1);
	for(int i=1; i<=N; i++) printf("%d ", ans[i]);
}

Compilation message (stderr)

swap.cpp: In function 'int solve(int, int)':
swap.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:127: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]);
                          ~~~~~^~~~~~~~~~~~~
swap.cpp: In function 'int solve(int, int)':
swap.cpp:77:6: warning: 'flag' may be used uninitialized in this function [-Wmaybe-uninitialized]
   mem=flag;
   ~~~^~~~~

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