oj.uz

Submission #76600

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

const int mxN=2e5, MGC1=1e6;
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 34 ms 34808 KB Output is correct
2 Correct 33 ms 34872 KB Output is correct
3 Correct 35 ms 35004 KB Output is correct
4 Correct 33 ms 35004 KB Output is correct
5 Correct 32 ms 35004 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34808 KB Output is correct
2 Correct 33 ms 34872 KB Output is correct
3 Correct 35 ms 35004 KB Output is correct
4 Correct 33 ms 35004 KB Output is correct
5 Correct 32 ms 35004 KB Output is correct
6 Correct 33 ms 35004 KB Output is correct
7 Correct 33 ms 35004 KB Output is correct
8 Correct 34 ms 35008 KB Output is correct
9 Correct 34 ms 35056 KB Output is correct
10 Correct 33 ms 35060 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34808 KB Output is correct
2 Correct 33 ms 34872 KB Output is correct
3 Correct 35 ms 35004 KB Output is correct
4 Correct 33 ms 35004 KB Output is correct
5 Correct 32 ms 35004 KB Output is correct
6 Correct 33 ms 35004 KB Output is correct
7 Correct 33 ms 35004 KB Output is correct
8 Correct 34 ms 35008 KB Output is correct
9 Correct 34 ms 35056 KB Output is correct
10 Correct 33 ms 35060 KB Output is correct
11 Correct 34 ms 35336 KB Output is correct
12 Correct 36 ms 35440 KB Output is correct
13 Correct 42 ms 35440 KB Output is correct
14 Correct 36 ms 35872 KB Output is correct
15 Correct 40 ms 35872 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34808 KB Output is correct
2 Correct 33 ms 34872 KB Output is correct
3 Correct 35 ms 35004 KB Output is correct
4 Correct 33 ms 35004 KB Output is correct
5 Correct 32 ms 35004 KB Output is correct
6 Correct 33 ms 35004 KB Output is correct
7 Correct 33 ms 35004 KB Output is correct
8 Correct 34 ms 35008 KB Output is correct
9 Correct 34 ms 35056 KB Output is correct
10 Correct 33 ms 35060 KB Output is correct
11 Correct 34 ms 35336 KB Output is correct
12 Correct 36 ms 35440 KB Output is correct
13 Correct 42 ms 35440 KB Output is correct
14 Correct 36 ms 35872 KB Output is correct
15 Correct 40 ms 35872 KB Output is correct
16 Correct 103 ms 50440 KB Output is correct
17 Correct 108 ms 50440 KB Output is correct
18 Correct 114 ms 51076 KB Output is correct
19 Correct 439 ms 105844 KB Output is correct
20 Correct 363 ms 105844 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34808 KB Output is correct
2 Correct 33 ms 34872 KB Output is correct
3 Correct 35 ms 35004 KB Output is correct
4 Correct 33 ms 35004 KB Output is correct
5 Correct 32 ms 35004 KB Output is correct
6 Correct 33 ms 35004 KB Output is correct
7 Correct 33 ms 35004 KB Output is correct
8 Correct 34 ms 35008 KB Output is correct
9 Correct 34 ms 35056 KB Output is correct
10 Correct 33 ms 35060 KB Output is correct
11 Correct 34 ms 35336 KB Output is correct
12 Correct 36 ms 35440 KB Output is correct
13 Correct 42 ms 35440 KB Output is correct
14 Correct 36 ms 35872 KB Output is correct
15 Correct 40 ms 35872 KB Output is correct
16 Correct 103 ms 50440 KB Output is correct
17 Correct 108 ms 50440 KB Output is correct
18 Correct 114 ms 51076 KB Output is correct
19 Correct 439 ms 105844 KB Output is correct
20 Correct 363 ms 105844 KB Output is correct
21 Correct 358 ms 105844 KB Output is correct
22 Correct 347 ms 105844 KB Output is correct
23 Correct 367 ms 105844 KB Output is correct
24 Execution timed out 1083 ms 238404 KB Time limit exceeded
25 Halted 0 ms 0 KB -