oj.uz

Submission #260045

# Submission time Handle Problem Language Result Execution time Memory
260045 2020-08-09T06:20:54 Z arnold518 Swap (BOI16_swap) C++14
48 / 100
 269 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];

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

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> ret1, ret2;
		vector<int> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
		ret1.push_back(A[now*2+1]);
		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++) ret1.push_back(p1[i]);
			for(int t=0; t<(1<<k) && j<q1.size(); t++, j++) ret1.push_back(q1[j]);
		}

		vector<int> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
		ret2.push_back(A[now*2+1]);
		for(int k=0, i=0, j=0; i<p2.size() || j<q2.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p2.size(); t++, i++) ret2.push_back(p2[i]);
			for(int t=0; t<(1<<k) && j<q2.size(); t++, j++) ret2.push_back(q2[j]);
		}
		ret=min(ret1, ret2);
		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());
	}

	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:71: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:71: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:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p1.size(); t++, i++) ret1.push_back(p1[i]);
                             ~^~~~~~~~~~
swap.cpp:74:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q1.size(); t++, j++) ret1.push_back(q1[j]);
                             ~^~~~~~~~~~
swap.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p2.size() || j<q2.size(); k++)
                          ~^~~~~~~~~~
swap.cpp:79:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p2.size() || j<q2.size(); k++)
                                         ~^~~~~~~~~~
swap.cpp:81:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p2.size(); t++, i++) ret2.push_back(p2[i]);
                             ~^~~~~~~~~~
swap.cpp:82:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q2.size(); t++, j++) ret2.push_back(q2[j]);
                             ~^~~~~~~~~~
swap.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:92: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 144 ms 239864 KB Output is correct
2 Correct 147 ms 239848 KB Output is correct
3 Correct 155 ms 239992 KB Output is correct
4 Correct 149 ms 239992 KB Output is correct
5 Correct 146 ms 239992 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 239864 KB Output is correct
2 Correct 147 ms 239848 KB Output is correct
3 Correct 155 ms 239992 KB Output is correct
4 Correct 149 ms 239992 KB Output is correct
5 Correct 146 ms 239992 KB Output is correct
6 Correct 149 ms 239872 KB Output is correct
7 Correct 145 ms 239812 KB Output is correct
8 Correct 144 ms 239864 KB Output is correct
9 Correct 161 ms 239868 KB Output is correct
10 Correct 160 ms 239864 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 239864 KB Output is correct
2 Correct 147 ms 239848 KB Output is correct
3 Correct 155 ms 239992 KB Output is correct
4 Correct 149 ms 239992 KB Output is correct
5 Correct 146 ms 239992 KB Output is correct
6 Correct 149 ms 239872 KB Output is correct
7 Correct 145 ms 239812 KB Output is correct
8 Correct 144 ms 239864 KB Output is correct
9 Correct 161 ms 239868 KB Output is correct
10 Correct 160 ms 239864 KB Output is correct
11 Correct 147 ms 240120 KB Output is correct
12 Correct 148 ms 240236 KB Output is correct
13 Correct 158 ms 240124 KB Output is correct
14 Correct 148 ms 240376 KB Output is correct
15 Correct 150 ms 240504 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 239864 KB Output is correct
2 Correct 147 ms 239848 KB Output is correct
3 Correct 155 ms 239992 KB Output is correct
4 Correct 149 ms 239992 KB Output is correct
5 Correct 146 ms 239992 KB Output is correct
6 Correct 149 ms 239872 KB Output is correct
7 Correct 145 ms 239812 KB Output is correct
8 Correct 144 ms 239864 KB Output is correct
9 Correct 161 ms 239868 KB Output is correct
10 Correct 160 ms 239864 KB Output is correct
11 Correct 147 ms 240120 KB Output is correct
12 Correct 148 ms 240236 KB Output is correct
13 Correct 158 ms 240124 KB Output is correct
14 Correct 148 ms 240376 KB Output is correct
15 Correct 150 ms 240504 KB Output is correct
16 Correct 237 ms 258380 KB Output is correct
17 Correct 238 ms 257908 KB Output is correct
18 Correct 239 ms 258356 KB Output is correct
19 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 239864 KB Output is correct
2 Correct 147 ms 239848 KB Output is correct
3 Correct 155 ms 239992 KB Output is correct
4 Correct 149 ms 239992 KB Output is correct
5 Correct 146 ms 239992 KB Output is correct
6 Correct 149 ms 239872 KB Output is correct
7 Correct 145 ms 239812 KB Output is correct
8 Correct 144 ms 239864 KB Output is correct
9 Correct 161 ms 239868 KB Output is correct
10 Correct 160 ms 239864 KB Output is correct
11 Correct 147 ms 240120 KB Output is correct
12 Correct 148 ms 240236 KB Output is correct
13 Correct 158 ms 240124 KB Output is correct
14 Correct 148 ms 240376 KB Output is correct
15 Correct 150 ms 240504 KB Output is correct
16 Correct 237 ms 258380 KB Output is correct
17 Correct 238 ms 257908 KB Output is correct
18 Correct 239 ms 258356 KB Output is correct
19 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -