oj.uz

Submission #25738

# Submission time Handle Problem Language Result Execution time Memory
25738 2017-06-24T00:41:35 Z minimario Swap (BOI16_swap) C++14
100 / 100
 393 ms 27752 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 200005;
int sz;
 
int ar[MAX];
 
map<pair<int, int>, int >  memo;
int dp(int n, int v) {
	if (memo.find({n, v}) != memo.end()) { 
		return memo[{n, v}];
	}
	
	if (2*n+1 <= sz) {
		if (v < ar[2*n] && v < ar[2*n+1]) { }
		else if (ar[2*n] < v && ar[2*n] < ar[2*n+1]) {
			memo[{n, v}] = dp(2*n, v);
			return memo[{n, v}];
		}
		else if (ar[2*n+1] < ar[2*n] && ar[2*n+1] < v) {
			if (v > ar[2*n]) { 
				if (dp(2*n, ar[2*n]) < dp(2*n+1, ar[2*n])) {
					memo[{n, v}] = dp(2*n+1, v);
				}
				else { 
					memo[{n, v}] = dp(2*n, v);
				}
			}
			else { memo[{n, v}] = min(dp(2*n, v), dp(2*n+1, v)); }
			return memo[{n, v}];
		}
	}
	else if (2*n == sz && v > ar[2*n]) { 
		memo[{n, v}] = dp(2*n, v);
		return memo[{n, v}];
	}
	memo[{n, v}] = n;
	return n;
}
 
void go(int n) {
	if (2*n+1 <= sz) {
		if (ar[n] < ar[2*n] && ar[n] < ar[2*n+1]) { }
		else if (ar[2*n] < ar[n] && ar[2*n] < ar[2*n+1]) {
			swap(ar[n], ar[2*n]); 
		}
		else if (ar[2*n+1] < ar[2*n] && ar[2*n+1] < ar[n]) {
			int mini = min(ar[n], ar[2*n]);
			int maxi = max(ar[n], ar[2*n]);
			int pos1 = dp(2*n, mini);
			int pos2 = dp(2*n+1, mini);
			ar[n] = ar[2*n+1];
			if (pos1 < pos2) { ar[2*n] = mini; ar[2*n+1] = maxi; }
			else { ar[2*n] = maxi; ar[2*n+1] = mini; }
		}
		go(2*n);
		go(2*n+1);
	}
	else if (2*n == sz && ar[n] > ar[2*n]) { swap(ar[n], ar[2*n]); }
}
 
int main(int argc, char const *argv[])
{
	scanf("%d", &sz);
	for (int i = 1; i <= sz; ++i)
	{
		scanf("%d", &ar[i]);
	}
	go(1);
	for (int i = 1; i <= sz; ++i)
	{
		printf("%d", ar[i]);
		if (i != sz) { printf(" "); }
		else { printf("\n"); }
	}
	return 0;
}

Compilation message

swap.cpp: In function 'int main(int, const char**)':
swap.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &sz);
                  ^
swap.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ar[i]);
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct
11 Correct 0 ms 2804 KB Output is correct
12 Correct 0 ms 2936 KB Output is correct
13 Correct 0 ms 2804 KB Output is correct
14 Correct 0 ms 2936 KB Output is correct
15 Correct 0 ms 2936 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct
11 Correct 0 ms 2804 KB Output is correct
12 Correct 0 ms 2936 KB Output is correct
13 Correct 0 ms 2804 KB Output is correct
14 Correct 0 ms 2936 KB Output is correct
15 Correct 0 ms 2936 KB Output is correct
16 Correct 29 ms 5180 KB Output is correct
17 Correct 49 ms 5180 KB Output is correct
18 Correct 26 ms 5180 KB Output is correct
19 Correct 83 ms 9008 KB Output is correct
20 Correct 89 ms 9008 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct
5 Correct 0 ms 2804 KB Output is correct
6 Correct 0 ms 2804 KB Output is correct
7 Correct 0 ms 2804 KB Output is correct
8 Correct 0 ms 2804 KB Output is correct
9 Correct 0 ms 2804 KB Output is correct
10 Correct 0 ms 2804 KB Output is correct
11 Correct 0 ms 2804 KB Output is correct
12 Correct 0 ms 2936 KB Output is correct
13 Correct 0 ms 2804 KB Output is correct
14 Correct 0 ms 2936 KB Output is correct
15 Correct 0 ms 2936 KB Output is correct
16 Correct 29 ms 5180 KB Output is correct
17 Correct 49 ms 5180 KB Output is correct
18 Correct 26 ms 5180 KB Output is correct
19 Correct 83 ms 9008 KB Output is correct
20 Correct 89 ms 9008 KB Output is correct
21 Correct 166 ms 12176 KB Output is correct
22 Correct 139 ms 12176 KB Output is correct
23 Correct 143 ms 12176 KB Output is correct
24 Correct 393 ms 27752 KB Output is correct
25 Correct 363 ms 27752 KB Output is correct