oj.uz

Submission #76595

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

const int mxN=2e5, MGC1=70000*18*2;
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;
			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 62 ms 70420 KB Output is correct
2 Correct 62 ms 70528 KB Output is correct
3 Correct 65 ms 70592 KB Output is correct
4 Correct 63 ms 70832 KB Output is correct
5 Correct 65 ms 70868 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 70420 KB Output is correct
2 Correct 62 ms 70528 KB Output is correct
3 Correct 65 ms 70592 KB Output is correct
4 Correct 63 ms 70832 KB Output is correct
5 Correct 65 ms 70868 KB Output is correct
6 Correct 63 ms 70932 KB Output is correct
7 Correct 64 ms 70956 KB Output is correct
8 Correct 63 ms 70956 KB Output is correct
9 Correct 68 ms 71060 KB Output is correct
10 Correct 61 ms 71060 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 70420 KB Output is correct
2 Correct 62 ms 70528 KB Output is correct
3 Correct 65 ms 70592 KB Output is correct
4 Correct 63 ms 70832 KB Output is correct
5 Correct 65 ms 70868 KB Output is correct
6 Correct 63 ms 70932 KB Output is correct
7 Correct 64 ms 70956 KB Output is correct
8 Correct 63 ms 70956 KB Output is correct
9 Correct 68 ms 71060 KB Output is correct
10 Correct 61 ms 71060 KB Output is correct
11 Correct 63 ms 71100 KB Output is correct
12 Correct 65 ms 71236 KB Output is correct
13 Correct 63 ms 71244 KB Output is correct
14 Correct 66 ms 71624 KB Output is correct
15 Correct 65 ms 71708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 70420 KB Output is correct
2 Correct 62 ms 70528 KB Output is correct
3 Correct 65 ms 70592 KB Output is correct
4 Correct 63 ms 70832 KB Output is correct
5 Correct 65 ms 70868 KB Output is correct
6 Correct 63 ms 70932 KB Output is correct
7 Correct 64 ms 70956 KB Output is correct
8 Correct 63 ms 70956 KB Output is correct
9 Correct 68 ms 71060 KB Output is correct
10 Correct 61 ms 71060 KB Output is correct
11 Correct 63 ms 71100 KB Output is correct
12 Correct 65 ms 71236 KB Output is correct
13 Correct 63 ms 71244 KB Output is correct
14 Correct 66 ms 71624 KB Output is correct
15 Correct 65 ms 71708 KB Output is correct
16 Correct 136 ms 86396 KB Output is correct
17 Correct 131 ms 86396 KB Output is correct
18 Correct 128 ms 87212 KB Output is correct
19 Correct 380 ms 141740 KB Output is correct
20 Correct 370 ms 141740 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 70420 KB Output is correct
2 Correct 62 ms 70528 KB Output is correct
3 Correct 65 ms 70592 KB Output is correct
4 Correct 63 ms 70832 KB Output is correct
5 Correct 65 ms 70868 KB Output is correct
6 Correct 63 ms 70932 KB Output is correct
7 Correct 64 ms 70956 KB Output is correct
8 Correct 63 ms 70956 KB Output is correct
9 Correct 68 ms 71060 KB Output is correct
10 Correct 61 ms 71060 KB Output is correct
11 Correct 63 ms 71100 KB Output is correct
12 Correct 65 ms 71236 KB Output is correct
13 Correct 63 ms 71244 KB Output is correct
14 Correct 66 ms 71624 KB Output is correct
15 Correct 65 ms 71708 KB Output is correct
16 Correct 136 ms 86396 KB Output is correct
17 Correct 131 ms 86396 KB Output is correct
18 Correct 128 ms 87212 KB Output is correct
19 Correct 380 ms 141740 KB Output is correct
20 Correct 370 ms 141740 KB Output is correct
21 Correct 351 ms 141740 KB Output is correct
22 Correct 350 ms 141740 KB Output is correct
23 Correct 348 ms 141740 KB Output is correct
24 Runtime error 811 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -