oj.uz

Submission #76602

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

const int mxN=2e5, MGC1=7e5;
int n, a[mxN+1], cdi;
unordered_map<int, int> di[mxN+1];
vector<int> dp[MGC1], 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]=-1;
}

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=cdi;
			cdi=(cdi+1)%MGC1;
			dp[c].clear();
			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};
		}
	}
	for(int b : gd(1, a[1]))
		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 25 ms 27768 KB Output is correct
2 Correct 26 ms 27876 KB Output is correct
3 Correct 26 ms 27876 KB Output is correct
4 Correct 28 ms 27876 KB Output is correct
5 Correct 26 ms 28024 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27768 KB Output is correct
2 Correct 26 ms 27876 KB Output is correct
3 Correct 26 ms 27876 KB Output is correct
4 Correct 28 ms 27876 KB Output is correct
5 Correct 26 ms 28024 KB Output is correct
6 Correct 29 ms 28024 KB Output is correct
7 Correct 27 ms 28024 KB Output is correct
8 Correct 26 ms 28024 KB Output is correct
9 Correct 25 ms 28024 KB Output is correct
10 Correct 25 ms 28024 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27768 KB Output is correct
2 Correct 26 ms 27876 KB Output is correct
3 Correct 26 ms 27876 KB Output is correct
4 Correct 28 ms 27876 KB Output is correct
5 Correct 26 ms 28024 KB Output is correct
6 Correct 29 ms 28024 KB Output is correct
7 Correct 27 ms 28024 KB Output is correct
8 Correct 26 ms 28024 KB Output is correct
9 Correct 25 ms 28024 KB Output is correct
10 Correct 25 ms 28024 KB Output is correct
11 Correct 27 ms 28252 KB Output is correct
12 Correct 29 ms 28268 KB Output is correct
13 Correct 28 ms 28268 KB Output is correct
14 Correct 30 ms 28668 KB Output is correct
15 Correct 29 ms 28792 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27768 KB Output is correct
2 Correct 26 ms 27876 KB Output is correct
3 Correct 26 ms 27876 KB Output is correct
4 Correct 28 ms 27876 KB Output is correct
5 Correct 26 ms 28024 KB Output is correct
6 Correct 29 ms 28024 KB Output is correct
7 Correct 27 ms 28024 KB Output is correct
8 Correct 26 ms 28024 KB Output is correct
9 Correct 25 ms 28024 KB Output is correct
10 Correct 25 ms 28024 KB Output is correct
11 Correct 27 ms 28252 KB Output is correct
12 Correct 29 ms 28268 KB Output is correct
13 Correct 28 ms 28268 KB Output is correct
14 Correct 30 ms 28668 KB Output is correct
15 Correct 29 ms 28792 KB Output is correct
16 Correct 94 ms 42980 KB Output is correct
17 Correct 94 ms 42980 KB Output is correct
18 Correct 99 ms 43256 KB Output is correct
19 Correct 379 ms 97228 KB Output is correct
20 Correct 335 ms 97228 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27768 KB Output is correct
2 Correct 26 ms 27876 KB Output is correct
3 Correct 26 ms 27876 KB Output is correct
4 Correct 28 ms 27876 KB Output is correct
5 Correct 26 ms 28024 KB Output is correct
6 Correct 29 ms 28024 KB Output is correct
7 Correct 27 ms 28024 KB Output is correct
8 Correct 26 ms 28024 KB Output is correct
9 Correct 25 ms 28024 KB Output is correct
10 Correct 25 ms 28024 KB Output is correct
11 Correct 27 ms 28252 KB Output is correct
12 Correct 29 ms 28268 KB Output is correct
13 Correct 28 ms 28268 KB Output is correct
14 Correct 30 ms 28668 KB Output is correct
15 Correct 29 ms 28792 KB Output is correct
16 Correct 94 ms 42980 KB Output is correct
17 Correct 94 ms 42980 KB Output is correct
18 Correct 99 ms 43256 KB Output is correct
19 Correct 379 ms 97228 KB Output is correct
20 Correct 335 ms 97228 KB Output is correct
21 Correct 330 ms 97228 KB Output is correct
22 Correct 337 ms 97228 KB Output is correct
23 Correct 389 ms 97228 KB Output is correct
24 Execution timed out 1091 ms 223348 KB Time limit exceeded
25 Halted 0 ms 0 KB -