Submission #260040

#	Time	Username	Problem	Language	Result	Execution time	Memory
260040		arnold518	Swap (BOI16_swap)	C++14	48 / 100	50 ms	49144 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 = 1000;

int N, A[MAXN+10];

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

vector<pii> &solve(int now, int pp)
{
	if(vis[now][pp]) return dp[now][pp];
	vis[now][pp]=1;
	vector<pii> &ret=dp[now][pp];

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

	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		vector<pii> &p=solve(now*2, now*2), &q=solve(now*2+1, now*2+1);
		ret.resize(p.size()+q.size()+1);
		ret[0]={now, A[pp]};
		merge(p.begin(), p.end(), q.begin(), q.end(), ret.begin()+1);
		return ret;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		vector<pii> &p=solve(now*2, pp), &q=solve(now*2+1, now*2+1);
		ret.resize(p.size()+q.size()+1);
		ret[0]={now, A[now*2]};
		merge(p.begin(), p.end(), q.begin(), q.end(), ret.begin()+1);
		return ret;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		vector<pii> ret1, ret2;
		vector<pii> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
		ret1.resize(p1.size()+q1.size()+1);
		ret1[0]={now, A[now*2+1]};
		merge(p1.begin(), p1.end(), q1.begin(), q1.end(), ret1.begin()+1);

		vector<pii> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
		ret2.resize(p2.size()+q2.size()+1);
		ret2[0]={now, A[now*2+1]};
		merge(p2.begin(), p2.end(), q2.begin(), q2.end(), ret2.begin()+1);
		ret=min(ret1, ret2);
		return ret;
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);

	vector<pii> ans=solve(1, 1);
	for(auto it : ans) printf("%d ", it.second);
}

Compilation message (stderr)

swap.cpp: In function 'std::vector<std::pair<int, int> >& solve(int, int)':
swap.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:77: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