oj.uz

Submission #76607

# Submission time Handle Problem Language Result Execution time Memory
76607 2018-09-15T07:21:35 Z tmwilliamlin168 Swap (BOI16_swap) C++14
68 / 100
 1000 ms 251584 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;

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];
	for(int i=n; i; --i) {
		for(int j=0; i>>j; ++j) {
			for(int k=0; k<1+((i>>j&1)&&i>>j>1); ++k) {
				int b=i>>j^k, c=j*2+k;
				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][c+2]);
						mrg(v2, dp[2*i][c+2], dp[2*i+1][1]);
						dp[i][c]=min(v1, v2);
					} else {
						dp[i][c]={min(a[b], a[2*i])};
						mrg(dp[i][c], dp[2*i][a[b]>a[2*i]?c+2:0], dp[2*i+1][0]);
					}
				} else if(2*i<=n)
					dp[i][c]={min(a[b], a[2*i]), max(a[b], a[2*i])};
				else
					dp[i][c]={a[b]};
			}
		}
		if(2*i+1<=n)
			for(int j=0; j<2; ++j)
				for(int k=0; k<36; ++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:9: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:9: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:10:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<l&&i+k<a.size(); ++k)
                     ~~~^~~~~~~~~
swap.cpp:12: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 150 ms 169544 KB Output is correct
2 Correct 150 ms 169544 KB Output is correct
3 Correct 153 ms 169544 KB Output is correct
4 Correct 145 ms 169572 KB Output is correct
5 Correct 149 ms 169760 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 169544 KB Output is correct
2 Correct 150 ms 169544 KB Output is correct
3 Correct 153 ms 169544 KB Output is correct
4 Correct 145 ms 169572 KB Output is correct
5 Correct 149 ms 169760 KB Output is correct
6 Correct 149 ms 169760 KB Output is correct
7 Correct 144 ms 169760 KB Output is correct
8 Correct 151 ms 169760 KB Output is correct
9 Correct 148 ms 169760 KB Output is correct
10 Correct 159 ms 169760 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 169544 KB Output is correct
2 Correct 150 ms 169544 KB Output is correct
3 Correct 153 ms 169544 KB Output is correct
4 Correct 145 ms 169572 KB Output is correct
5 Correct 149 ms 169760 KB Output is correct
6 Correct 149 ms 169760 KB Output is correct
7 Correct 144 ms 169760 KB Output is correct
8 Correct 151 ms 169760 KB Output is correct
9 Correct 148 ms 169760 KB Output is correct
10 Correct 159 ms 169760 KB Output is correct
11 Correct 152 ms 169836 KB Output is correct
12 Correct 153 ms 169836 KB Output is correct
13 Correct 158 ms 169836 KB Output is correct
14 Correct 154 ms 169908 KB Output is correct
15 Correct 152 ms 169964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 169544 KB Output is correct
2 Correct 150 ms 169544 KB Output is correct
3 Correct 153 ms 169544 KB Output is correct
4 Correct 145 ms 169572 KB Output is correct
5 Correct 149 ms 169760 KB Output is correct
6 Correct 149 ms 169760 KB Output is correct
7 Correct 144 ms 169760 KB Output is correct
8 Correct 151 ms 169760 KB Output is correct
9 Correct 148 ms 169760 KB Output is correct
10 Correct 159 ms 169760 KB Output is correct
11 Correct 152 ms 169836 KB Output is correct
12 Correct 153 ms 169836 KB Output is correct
13 Correct 158 ms 169836 KB Output is correct
14 Correct 154 ms 169908 KB Output is correct
15 Correct 152 ms 169964 KB Output is correct
16 Correct 394 ms 187820 KB Output is correct
17 Correct 405 ms 187820 KB Output is correct
18 Correct 420 ms 187820 KB Output is correct
19 Correct 374 ms 187932 KB Output is correct
20 Correct 379 ms 187932 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 169544 KB Output is correct
2 Correct 150 ms 169544 KB Output is correct
3 Correct 153 ms 169544 KB Output is correct
4 Correct 145 ms 169572 KB Output is correct
5 Correct 149 ms 169760 KB Output is correct
6 Correct 149 ms 169760 KB Output is correct
7 Correct 144 ms 169760 KB Output is correct
8 Correct 151 ms 169760 KB Output is correct
9 Correct 148 ms 169760 KB Output is correct
10 Correct 159 ms 169760 KB Output is correct
11 Correct 152 ms 169836 KB Output is correct
12 Correct 153 ms 169836 KB Output is correct
13 Correct 158 ms 169836 KB Output is correct
14 Correct 154 ms 169908 KB Output is correct
15 Correct 152 ms 169964 KB Output is correct
16 Correct 394 ms 187820 KB Output is correct
17 Correct 405 ms 187820 KB Output is correct
18 Correct 420 ms 187820 KB Output is correct
19 Correct 374 ms 187932 KB Output is correct
20 Correct 379 ms 187932 KB Output is correct
21 Execution timed out 1076 ms 251584 KB Time limit exceeded
22 Halted 0 ms 0 KB -