답안 #56897 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56897	2018-07-13T06:18:20 Z	ainta	Swap (BOI16_swap)	C++17	48 / 100	1000 ms	82264 KB

swap

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 262144
using namespace std;
int w[262144], n, res[262144];
vector<int>P[262144], D[262144], U[262144];
int Get(int nd, int x) {
	int t = lower_bound(P[nd].begin(), P[nd].end(), x + 1) - P[nd].begin();
	if (t == 0)return nd;
	return D[nd][t - 1];
}
void Do(int a) {
	if (a * 2 >= 262144) return;
	int c1 = a * 2, c2 = a * 2 + 1;
	Do(c1);
	Do(c2);
	for (auto &t : P[c1])P[a].push_back(t);
	for (auto &t : P[c2])P[a].push_back(t);
	P[a].push_back(w[c1]);
	P[a].push_back(w[c2]);
	sort(P[a].begin(), P[a].end());
	if (a == 1) {
		int t = -1;
	}
	for (auto &x : P[a]) {
		if (x < w[c1] && x < w[c2]) {
			D[a].push_back(a);
			U[a].push_back(0);
		}
		else if (w[c1] <= x && w[c1] < w[c2]) {
			int num = Get(c1, x);
			D[a].push_back(num);
			U[a].push_back(1);
		}
		else {
			int a1 = Get(c1, w[c1]);
			int a2 = Get(c2, x);
			int b1 = Get(c1, x);
			int b2 = Get(c2, w[c1]);
			int ck = 0;
			if (min(a1, a2) != min(b1, b2)) {
				if (min(a1, a2) < min(b1, b2))ck = 1;
				else ck = 2;
			}
			else{
				if ((w[c1] <= x) == (a1 < b2)) ck = 1;
				else ck = 2;
			}
			if (ck == 1) D[a].push_back(a2);
			else D[a].push_back(b1);
			U[a].push_back(ck + 1);
		}
	}
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)scanf("%d", &w[i]);
	for (i = n + 1; i <= 262143; i++)w[i] = i;
	Do(1);
	for (i = 1; i <= n; i++) {
		int t = lower_bound(P[i].begin(), P[i].end(), w[i]) - P[i].begin();
		if (t == 0) continue;
		t--;
		if (U[i][t] == 1) {
			swap(w[i], w[i * 2]);
		}
		if (U[i][t] == 2) {
			swap(w[i], w[i * 2 + 1]);
		}
		if (U[i][t] == 3) {
			swap(w[i], w[i * 2]);
			swap(w[i], w[i * 2 + 1]);
		}
	}
	for (i = 1; i <= n; i++)printf("%d ", w[i]);
}

Compilation message

swap.cpp: In function 'void Do(int)':
swap.cpp:24:7: warning: unused variable 't' [-Wunused-variable]
   int t = -1;
       ^
swap.cpp: In function 'int main()':
swap.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++)scanf("%d", &w[i]);
                          ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	649 ms	79688 KB	Output is correct
2	Correct	692 ms	79860 KB	Output is correct
3	Correct	769 ms	79956 KB	Output is correct
4	Correct	742 ms	80280 KB	Output is correct
5	Correct	810 ms	80280 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	649 ms	79688 KB	Output is correct
2	Correct	692 ms	79860 KB	Output is correct
3	Correct	769 ms	79956 KB	Output is correct
4	Correct	742 ms	80280 KB	Output is correct
5	Correct	810 ms	80280 KB	Output is correct
6	Correct	776 ms	80292 KB	Output is correct
7	Correct	796 ms	80292 KB	Output is correct
8	Correct	769 ms	80292 KB	Output is correct
9	Correct	880 ms	80292 KB	Output is correct
10	Correct	857 ms	80292 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	649 ms	79688 KB	Output is correct
2	Correct	692 ms	79860 KB	Output is correct
3	Correct	769 ms	79956 KB	Output is correct
4	Correct	742 ms	80280 KB	Output is correct
5	Correct	810 ms	80280 KB	Output is correct
6	Correct	776 ms	80292 KB	Output is correct
7	Correct	796 ms	80292 KB	Output is correct
8	Correct	769 ms	80292 KB	Output is correct
9	Correct	880 ms	80292 KB	Output is correct
10	Correct	857 ms	80292 KB	Output is correct
11	Correct	797 ms	80292 KB	Output is correct
12	Correct	825 ms	80292 KB	Output is correct
13	Correct	687 ms	80292 KB	Output is correct
14	Correct	848 ms	80292 KB	Output is correct
15	Correct	851 ms	80292 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	649 ms	79688 KB	Output is correct
2	Correct	692 ms	79860 KB	Output is correct
3	Correct	769 ms	79956 KB	Output is correct
4	Correct	742 ms	80280 KB	Output is correct
5	Correct	810 ms	80280 KB	Output is correct
6	Correct	776 ms	80292 KB	Output is correct
7	Correct	796 ms	80292 KB	Output is correct
8	Correct	769 ms	80292 KB	Output is correct
9	Correct	880 ms	80292 KB	Output is correct
10	Correct	857 ms	80292 KB	Output is correct
11	Correct	797 ms	80292 KB	Output is correct
12	Correct	825 ms	80292 KB	Output is correct
13	Correct	687 ms	80292 KB	Output is correct
14	Correct	848 ms	80292 KB	Output is correct
15	Correct	851 ms	80292 KB	Output is correct
16	Correct	940 ms	80888 KB	Output is correct
17	Correct	952 ms	81116 KB	Output is correct
18	Correct	872 ms	81432 KB	Output is correct
19	Correct	925 ms	81852 KB	Output is correct
20	Execution timed out	1083 ms	82264 KB	Time limit exceeded

Subtask #5
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	649 ms	79688 KB	Output is correct
2	Correct	692 ms	79860 KB	Output is correct
3	Correct	769 ms	79956 KB	Output is correct
4	Correct	742 ms	80280 KB	Output is correct
5	Correct	810 ms	80280 KB	Output is correct
6	Correct	776 ms	80292 KB	Output is correct
7	Correct	796 ms	80292 KB	Output is correct
8	Correct	769 ms	80292 KB	Output is correct
9	Correct	880 ms	80292 KB	Output is correct
10	Correct	857 ms	80292 KB	Output is correct
11	Correct	797 ms	80292 KB	Output is correct
12	Correct	825 ms	80292 KB	Output is correct
13	Correct	687 ms	80292 KB	Output is correct
14	Correct	848 ms	80292 KB	Output is correct
15	Correct	851 ms	80292 KB	Output is correct
16	Correct	940 ms	80888 KB	Output is correct
17	Correct	952 ms	81116 KB	Output is correct
18	Correct	872 ms	81432 KB	Output is correct
19	Correct	925 ms	81852 KB	Output is correct
20	Execution timed out	1083 ms	82264 KB	Time limit exceeded

답안 #56897

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 11.0 / 11.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 20.0

Subtask #5 0 / 32.0

Subtask #1
10.0 / 10.0

Subtask #2
11.0 / 11.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 20.0

Subtask #5
0 / 32.0