oj.uz

Submission #76611

# Submission time Handle Problem Language Result Execution time Memory
76611 2018-09-15T07:30:49 Z tmwilliamlin168 Swap (BOI16_swap) C++14
100 / 100
 936 ms 232748 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5;
int n, a[mxN+1];
vector<int> dp[mxN+1][36], v1, v2;
bool v[mxN+1][36];

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]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=1; i<=n; ++i)
		cin >> a[i];
	v[1][0]=1;
	for(int i=1; 2*i+1<=n; ++i) {
		for(int j=0; j<36; ++j) {
			if(!v[i][j])
				continue;
			int b=i>>j/2^j&1;
			if(2*i+1<=n) {
				if(a[2*i+1]<a[b]&&a[2*i+1]<a[2*i])
					v[2*i][0]=v[2*i+1][j+2]=v[2*i][j+2]=v[2*i+1][1]=1;
				else
					v[2*i][a[b]>a[2*i]?j+2:0]=v[2*i+1][0]=1;
			}
		}
	}
	for(int i=n; i; --i) {
		for(int j=0; j<36; ++j) {
			if(!v[i][j])
				continue;
			int b=i>>j/2^j&1;
			if(2*i+1<=n) {
				if(a[2*i+1]<a[b]&&a[2*i+1]<a[2*i]) {
					v1={a[2*i+1]};
					v2={a[2*i+1]};
					mrg(v1, dp[2*i][0], dp[2*i+1][j+2]);
					mrg(v2, dp[2*i][j+2], dp[2*i+1][1]);
					dp[i][j]=min(v1, v2);
				} else {
					dp[i][j]={min(a[b], a[2*i])};
					mrg(dp[i][j], dp[2*i][a[b]>a[2*i]?j+2:0], dp[2*i+1][0]);
				}
			} else if(2*i<=n)
				dp[i][j]={min(a[b], a[2*i]), max(a[b], a[2*i])};
			else
				dp[i][j]={a[b]};
		}
		if(2*i+1<=n)
			for(int j=0; j<2; ++j)
				for(int k=0; k<36; ++k)
					if(v[2*i+j][k])
						vector<int>().swap(dp[2*i+j][k]);
	}
	for(int b : dp[1][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)
                     ~~~^~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:30:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    int b=i>>j/2^j&1;
                 ~^~
swap.cpp:43:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    int b=i>>j/2^j&1;
                 ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 169464 KB Output is correct
2 Correct 155 ms 169656 KB Output is correct
3 Correct 150 ms 169656 KB Output is correct
4 Correct 154 ms 169656 KB Output is correct
5 Correct 148 ms 169656 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 169464 KB Output is correct
2 Correct 155 ms 169656 KB Output is correct
3 Correct 150 ms 169656 KB Output is correct
4 Correct 154 ms 169656 KB Output is correct
5 Correct 148 ms 169656 KB Output is correct
6 Correct 152 ms 169656 KB Output is correct
7 Correct 156 ms 169656 KB Output is correct
8 Correct 146 ms 169740 KB Output is correct
9 Correct 149 ms 169740 KB Output is correct
10 Correct 149 ms 169740 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 169464 KB Output is correct
2 Correct 155 ms 169656 KB Output is correct
3 Correct 150 ms 169656 KB Output is correct
4 Correct 154 ms 169656 KB Output is correct
5 Correct 148 ms 169656 KB Output is correct
6 Correct 152 ms 169656 KB Output is correct
7 Correct 156 ms 169656 KB Output is correct
8 Correct 146 ms 169740 KB Output is correct
9 Correct 149 ms 169740 KB Output is correct
10 Correct 149 ms 169740 KB Output is correct
11 Correct 169 ms 169788 KB Output is correct
12 Correct 150 ms 169824 KB Output is correct
13 Correct 150 ms 169824 KB Output is correct
14 Correct 150 ms 170036 KB Output is correct
15 Correct 149 ms 170036 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 169464 KB Output is correct
2 Correct 155 ms 169656 KB Output is correct
3 Correct 150 ms 169656 KB Output is correct
4 Correct 154 ms 169656 KB Output is correct
5 Correct 148 ms 169656 KB Output is correct
6 Correct 152 ms 169656 KB Output is correct
7 Correct 156 ms 169656 KB Output is correct
8 Correct 146 ms 169740 KB Output is correct
9 Correct 149 ms 169740 KB Output is correct
10 Correct 149 ms 169740 KB Output is correct
11 Correct 169 ms 169788 KB Output is correct
12 Correct 150 ms 169824 KB Output is correct
13 Correct 150 ms 169824 KB Output is correct
14 Correct 150 ms 170036 KB Output is correct
15 Correct 149 ms 170036 KB Output is correct
16 Correct 203 ms 173624 KB Output is correct
17 Correct 204 ms 173624 KB Output is correct
18 Correct 208 ms 173660 KB Output is correct
19 Correct 320 ms 183724 KB Output is correct
20 Correct 313 ms 183724 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 169464 KB Output is correct
2 Correct 155 ms 169656 KB Output is correct
3 Correct 150 ms 169656 KB Output is correct
4 Correct 154 ms 169656 KB Output is correct
5 Correct 148 ms 169656 KB Output is correct
6 Correct 152 ms 169656 KB Output is correct
7 Correct 156 ms 169656 KB Output is correct
8 Correct 146 ms 169740 KB Output is correct
9 Correct 149 ms 169740 KB Output is correct
10 Correct 149 ms 169740 KB Output is correct
11 Correct 169 ms 169788 KB Output is correct
12 Correct 150 ms 169824 KB Output is correct
13 Correct 150 ms 169824 KB Output is correct
14 Correct 150 ms 170036 KB Output is correct
15 Correct 149 ms 170036 KB Output is correct
16 Correct 203 ms 173624 KB Output is correct
17 Correct 204 ms 173624 KB Output is correct
18 Correct 208 ms 173660 KB Output is correct
19 Correct 320 ms 183724 KB Output is correct
20 Correct 313 ms 183724 KB Output is correct
21 Correct 414 ms 185132 KB Output is correct
22 Correct 408 ms 185260 KB Output is correct
23 Correct 423 ms 185260 KB Output is correct
24 Correct 930 ms 231524 KB Output is correct
25 Correct 936 ms 232748 KB Output is correct