답안 #25738 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25738	2017-06-24T00:41:35 Z	minimario	Swap (BOI16_swap)	C++14	100 / 100	393 ms	27752 KB

swap

#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

#	결과	메모리	Grader output
1	Correct	2804 KB	Output is correct
2	Correct	2804 KB	Output is correct
3	Correct	2804 KB	Output is correct
4	Correct	2804 KB	Output is correct
5	Correct	2804 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	메모리	Grader output
1	Correct	2804 KB	Output is correct
2	Correct	2804 KB	Output is correct
3	Correct	2804 KB	Output is correct
4	Correct	2804 KB	Output is correct
5	Correct	2804 KB	Output is correct
6	Correct	2804 KB	Output is correct
7	Correct	2804 KB	Output is correct
8	Correct	2804 KB	Output is correct
9	Correct	2804 KB	Output is correct
10	Correct	2804 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	메모리	Grader output
1	Correct	2804 KB	Output is correct
2	Correct	2804 KB	Output is correct
3	Correct	2804 KB	Output is correct
4	Correct	2804 KB	Output is correct
5	Correct	2804 KB	Output is correct
6	Correct	2804 KB	Output is correct
7	Correct	2804 KB	Output is correct
8	Correct	2804 KB	Output is correct
9	Correct	2804 KB	Output is correct
10	Correct	2804 KB	Output is correct
11	Correct	2804 KB	Output is correct
12	Correct	2936 KB	Output is correct
13	Correct	2804 KB	Output is correct
14	Correct	2936 KB	Output is correct
15	Correct	2936 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #25738

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 11.0 / 11.0

Subtask #3 27.0 / 27.0

Subtask #4 20.0 / 20.0

Subtask #5 32.0 / 32.0

Subtask #1
10.0 / 10.0

Subtask #2
11.0 / 11.0

Subtask #3
27.0 / 27.0

Subtask #4
20.0 / 20.0

Subtask #5
32.0 / 32.0