oj.uz

Submission #260052

# Submission time Handle Problem Language Result Execution time Memory
260052 2020-08-09T06:32:36 Z arnold518 Swap (BOI16_swap) C++14
68 / 100
 907 ms 262148 KB 
#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];

unordered_map<int, bool> vis[MAXN+10];
unordered_map<int, vector<int>> dp[MAXN+10];

vector<int> &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<int> &ret=dp[now][qq];

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

	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		vector<int> &p=solve(now*2, now*2), &q=solve(now*2+1, now*2+1);
		ret.push_back(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<int> &p=solve(now*2, pp), &q=solve(now*2+1, now*2+1);
		ret.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++) 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<int> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
		vector<int> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
		ret.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) 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<int> ans=solve(1, 1);
	for(auto it : ans) printf("%d ", it);
}

Compilation message

swap.cpp: In function 'std::vector<int>& solve(int, int)':
swap.cpp:48: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:48: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:50: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:51: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:59: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:59: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:61: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:62: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:72: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:72: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:74: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:85: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:99:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:104: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26880 KB Output is correct
2 Correct 18 ms 26880 KB Output is correct
3 Correct 18 ms 26880 KB Output is correct
4 Correct 18 ms 26880 KB Output is correct
5 Correct 21 ms 27008 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26880 KB Output is correct
2 Correct 18 ms 26880 KB Output is correct
3 Correct 18 ms 26880 KB Output is correct
4 Correct 18 ms 26880 KB Output is correct
5 Correct 21 ms 27008 KB Output is correct
6 Correct 18 ms 26880 KB Output is correct
7 Correct 21 ms 27008 KB Output is correct
8 Correct 19 ms 26880 KB Output is correct
9 Correct 18 ms 27008 KB Output is correct
10 Correct 18 ms 27008 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26880 KB Output is correct
2 Correct 18 ms 26880 KB Output is correct
3 Correct 18 ms 26880 KB Output is correct
4 Correct 18 ms 26880 KB Output is correct
5 Correct 21 ms 27008 KB Output is correct
6 Correct 18 ms 26880 KB Output is correct
7 Correct 21 ms 27008 KB Output is correct
8 Correct 19 ms 26880 KB Output is correct
9 Correct 18 ms 27008 KB Output is correct
10 Correct 18 ms 27008 KB Output is correct
11 Correct 21 ms 27392 KB Output is correct
12 Correct 21 ms 27520 KB Output is correct
13 Correct 20 ms 27392 KB Output is correct
14 Correct 25 ms 28288 KB Output is correct
15 Correct 24 ms 28280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26880 KB Output is correct
2 Correct 18 ms 26880 KB Output is correct
3 Correct 18 ms 26880 KB Output is correct
4 Correct 18 ms 26880 KB Output is correct
5 Correct 21 ms 27008 KB Output is correct
6 Correct 18 ms 26880 KB Output is correct
7 Correct 21 ms 27008 KB Output is correct
8 Correct 19 ms 26880 KB Output is correct
9 Correct 18 ms 27008 KB Output is correct
10 Correct 18 ms 27008 KB Output is correct
11 Correct 21 ms 27392 KB Output is correct
12 Correct 21 ms 27520 KB Output is correct
13 Correct 20 ms 27392 KB Output is correct
14 Correct 25 ms 28288 KB Output is correct
15 Correct 24 ms 28280 KB Output is correct
16 Correct 180 ms 56576 KB Output is correct
17 Correct 179 ms 56692 KB Output is correct
18 Correct 184 ms 56820 KB Output is correct
19 Correct 738 ms 144244 KB Output is correct
20 Correct 851 ms 143504 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26880 KB Output is correct
2 Correct 18 ms 26880 KB Output is correct
3 Correct 18 ms 26880 KB Output is correct
4 Correct 18 ms 26880 KB Output is correct
5 Correct 21 ms 27008 KB Output is correct
6 Correct 18 ms 26880 KB Output is correct
7 Correct 21 ms 27008 KB Output is correct
8 Correct 19 ms 26880 KB Output is correct
9 Correct 18 ms 27008 KB Output is correct
10 Correct 18 ms 27008 KB Output is correct
11 Correct 21 ms 27392 KB Output is correct
12 Correct 21 ms 27520 KB Output is correct
13 Correct 20 ms 27392 KB Output is correct
14 Correct 25 ms 28288 KB Output is correct
15 Correct 24 ms 28280 KB Output is correct
16 Correct 180 ms 56576 KB Output is correct
17 Correct 179 ms 56692 KB Output is correct
18 Correct 184 ms 56820 KB Output is correct
19 Correct 738 ms 144244 KB Output is correct
20 Correct 851 ms 143504 KB Output is correct
21 Correct 713 ms 151020 KB Output is correct
22 Correct 811 ms 151660 KB Output is correct
23 Correct 702 ms 152300 KB Output is correct
24 Runtime error 907 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -