oj.uz

Submission #76590

# Submission time Handle Problem Language Result Execution time Memory
76590 2018-09-15T06:13:43 Z tmwilliamlin168 Swap (BOI16_swap) C++14
68 / 100
 562 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5;
int n, a[mxN+1], cdi;
unordered_map<int, int> di[mxN+1];
vector<int> dp[mxN*18*2], v1, v2;

void mrg(vector<int> &v, vector<int> &a, vector<int> &b) {
	for(int l=1, i=0, j=0; i<a.size()||j<b.size(); i+=l, j+=l, l*=2) {
		for(int k=0; k<l&&i+k<a.size(); ++k)
			v.push_back(a[i+k]);
		for(int k=0; k<l&&j+k<b.size(); ++k)
			v.push_back(b[j+k]);
	}
}

void as(int i, int b) {
	if(di[i].find(b)==di[i].end())
		di[i][b]=cdi++;
}

vector<int>& gd(int i, int b) {
	return dp[di[i][b]];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=1; i<=n; ++i)
		cin >> a[i];
	as(1, a[1]);
	for(int i=1; 2*i+1<=n; ++i) {
		for(auto it=di[i].begin(); it!=di[i].end(); ++it) {
			int b=it->first;
			if(a[2*i+1]<b&&a[2*i+1]<a[2*i]) {
				as(2*i, a[2*i]);
				as(2*i+1, b);
				as(2*i, b);
				as(2*i+1, a[2*i]);
			} else {
				as(2*i, max(b, a[2*i]));
				as(2*i+1, a[2*i+1]);
			}
		}
	}
	for(int i=n; i; --i) {
		for(auto it=di[i].begin(); it!=di[i].end(); ++it) {
			int b=it->first, c=it->second;
			if(2*i+1<=n) {
				if(a[2*i+1]<b&&a[2*i+1]<a[2*i]) {
					v1={a[2*i+1]};
					v2={a[2*i+1]};
					mrg(v1, gd(2*i, a[2*i]), gd(2*i+1, b));
					mrg(v2, gd(2*i, b), gd(2*i+1, a[2*i]));
					dp[c]=min(v1, v2);
				} else {
					dp[c]={min(b, a[2*i])};
					mrg(dp[c], gd(2*i, max(b, a[2*i])), gd(2*i+1, a[2*i+1]));
				}
			} else if(2*i<=n)
				dp[c]={min(b, a[2*i]), max(b, a[2*i])};
			else
				dp[c]={b};
		}
		if(2*i+1<=n)
			for(int j=0; j<2; ++j)
				for(auto it=di[2*i+j].begin(); it!=di[2*i+j].end(); ++it)
					vector<int>().swap(dp[it->second]);
	}
	for(int b : dp[0])
		cout << b << " ";
}

Compilation message

swap.cpp: In function 'void mrg(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:10:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=1, i=0, j=0; i<a.size()||j<b.size(); i+=l, j+=l, l*=2) {
                         ~^~~~~~~~~
swap.cpp:10:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=1, i=0, j=0; i<a.size()||j<b.size(); i+=l, j+=l, l*=2) {
                                     ~^~~~~~~~~
swap.cpp:11:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<l&&i+k<a.size(); ++k)
                     ~~~^~~~~~~~~
swap.cpp:13:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<l&&j+k<b.size(); ++k)
                     ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 180316 KB Output is correct
2 Correct 166 ms 180508 KB Output is correct
3 Correct 156 ms 180720 KB Output is correct
4 Correct 160 ms 180864 KB Output is correct
5 Correct 155 ms 180864 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 180316 KB Output is correct
2 Correct 166 ms 180508 KB Output is correct
3 Correct 156 ms 180720 KB Output is correct
4 Correct 160 ms 180864 KB Output is correct
5 Correct 155 ms 180864 KB Output is correct
6 Correct 168 ms 180864 KB Output is correct
7 Correct 159 ms 180864 KB Output is correct
8 Correct 169 ms 181072 KB Output is correct
9 Correct 162 ms 181072 KB Output is correct
10 Correct 167 ms 181072 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 180316 KB Output is correct
2 Correct 166 ms 180508 KB Output is correct
3 Correct 156 ms 180720 KB Output is correct
4 Correct 160 ms 180864 KB Output is correct
5 Correct 155 ms 180864 KB Output is correct
6 Correct 168 ms 180864 KB Output is correct
7 Correct 159 ms 180864 KB Output is correct
8 Correct 169 ms 181072 KB Output is correct
9 Correct 162 ms 181072 KB Output is correct
10 Correct 167 ms 181072 KB Output is correct
11 Correct 163 ms 181072 KB Output is correct
12 Correct 161 ms 181072 KB Output is correct
13 Correct 157 ms 181072 KB Output is correct
14 Correct 164 ms 181472 KB Output is correct
15 Correct 164 ms 181472 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 180316 KB Output is correct
2 Correct 166 ms 180508 KB Output is correct
3 Correct 156 ms 180720 KB Output is correct
4 Correct 160 ms 180864 KB Output is correct
5 Correct 155 ms 180864 KB Output is correct
6 Correct 168 ms 180864 KB Output is correct
7 Correct 159 ms 180864 KB Output is correct
8 Correct 169 ms 181072 KB Output is correct
9 Correct 162 ms 181072 KB Output is correct
10 Correct 167 ms 181072 KB Output is correct
11 Correct 163 ms 181072 KB Output is correct
12 Correct 161 ms 181072 KB Output is correct
13 Correct 157 ms 181072 KB Output is correct
14 Correct 164 ms 181472 KB Output is correct
15 Correct 164 ms 181472 KB Output is correct
16 Correct 270 ms 189208 KB Output is correct
17 Correct 230 ms 189480 KB Output is correct
18 Correct 229 ms 190024 KB Output is correct
19 Correct 467 ms 223464 KB Output is correct
20 Correct 562 ms 223516 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 180316 KB Output is correct
2 Correct 166 ms 180508 KB Output is correct
3 Correct 156 ms 180720 KB Output is correct
4 Correct 160 ms 180864 KB Output is correct
5 Correct 155 ms 180864 KB Output is correct
6 Correct 168 ms 180864 KB Output is correct
7 Correct 159 ms 180864 KB Output is correct
8 Correct 169 ms 181072 KB Output is correct
9 Correct 162 ms 181072 KB Output is correct
10 Correct 167 ms 181072 KB Output is correct
11 Correct 163 ms 181072 KB Output is correct
12 Correct 161 ms 181072 KB Output is correct
13 Correct 157 ms 181072 KB Output is correct
14 Correct 164 ms 181472 KB Output is correct
15 Correct 164 ms 181472 KB Output is correct
16 Correct 270 ms 189208 KB Output is correct
17 Correct 230 ms 189480 KB Output is correct
18 Correct 229 ms 190024 KB Output is correct
19 Correct 467 ms 223464 KB Output is correct
20 Correct 562 ms 223516 KB Output is correct
21 Correct 448 ms 223516 KB Output is correct
22 Correct 460 ms 223516 KB Output is correct
23 Correct 466 ms 223516 KB Output is correct
24 Runtime error 519 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -