답안 #56899 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56899	2018-07-13T06:30:17 Z	ainta	Swap (BOI16_swap)	C++17	100 / 100	497 ms	90160 KB

swap

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 262144
using namespace std;
int w[262144], n, res[262144], R[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];
}
int Get2(int nd, int x) {
	if (x == 0)return nd;
	return D[nd][x - 1];
}
int A[262144], B[262144];
void Do(int a) {
	if (a * 2 >= 262144) {
		R[a] = a;
		return;
	}
	int c1 = a * 2, c2 = a * 2 + 1;
	Do(c1);
	Do(c2);
	int CA = 0, CB = 0;
	for (auto &t : P[c1]) if (t < w[c1])A[CA++] = t;
	A[CA++] = w[c1];
	for (auto &t : P[c1]) if (t > w[c1])A[CA++] = t;
	for (auto &t : P[c2]) if (t < w[c2])B[CB++] = t;
	B[CB++] = w[c2];
	for (auto &t : P[c2]) if (t > w[c2])B[CB++] = t;

	int pA = 0, pB = 0, ppA = 0, ppB = 0;
	int ta1 = Get(c1, w[c1]);
	int tb2 = Get(c2, w[c1]);
	while (pA < CA || pB < CB) {
		if (pB == CB || (pA < CA && A[pA] < B[pB])) {
			if (A[pA] != w[c1])ppA++;
			P[a].push_back(A[pA++]);
		}
		else {
			if (B[pB] != w[c2])ppB++;
			P[a].push_back(B[pB++]);
		}
		int x = P[a].back();
		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 = Get2(c1, ppA);
			D[a].push_back(num);
			U[a].push_back(1);
		}
		else {
			int a1 = ta1;
			int a2 = Get2(c2, ppB);
			int b1 = Get2(c1, ppA);
			int b2 =  tb2;
			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 'int main()':
swap.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:79: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	404 ms	80860 KB	Output is correct
2	Correct	337 ms	80860 KB	Output is correct
3	Correct	346 ms	80860 KB	Output is correct
4	Correct	291 ms	80860 KB	Output is correct
5	Correct	316 ms	80860 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	404 ms	80860 KB	Output is correct
2	Correct	337 ms	80860 KB	Output is correct
3	Correct	346 ms	80860 KB	Output is correct
4	Correct	291 ms	80860 KB	Output is correct
5	Correct	316 ms	80860 KB	Output is correct
6	Correct	431 ms	80860 KB	Output is correct
7	Correct	478 ms	80860 KB	Output is correct
8	Correct	303 ms	80860 KB	Output is correct
9	Correct	382 ms	81124 KB	Output is correct
10	Correct	336 ms	81124 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	404 ms	80860 KB	Output is correct
2	Correct	337 ms	80860 KB	Output is correct
3	Correct	346 ms	80860 KB	Output is correct
4	Correct	291 ms	80860 KB	Output is correct
5	Correct	316 ms	80860 KB	Output is correct
6	Correct	431 ms	80860 KB	Output is correct
7	Correct	478 ms	80860 KB	Output is correct
8	Correct	303 ms	80860 KB	Output is correct
9	Correct	382 ms	81124 KB	Output is correct
10	Correct	336 ms	81124 KB	Output is correct
11	Correct	315 ms	81124 KB	Output is correct
12	Correct	384 ms	81124 KB	Output is correct
13	Correct	375 ms	81124 KB	Output is correct
14	Correct	316 ms	81124 KB	Output is correct
15	Correct	335 ms	81124 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	404 ms	80860 KB	Output is correct
2	Correct	337 ms	80860 KB	Output is correct
3	Correct	346 ms	80860 KB	Output is correct
4	Correct	291 ms	80860 KB	Output is correct
5	Correct	316 ms	80860 KB	Output is correct
6	Correct	431 ms	80860 KB	Output is correct
7	Correct	478 ms	80860 KB	Output is correct
8	Correct	303 ms	80860 KB	Output is correct
9	Correct	382 ms	81124 KB	Output is correct
10	Correct	336 ms	81124 KB	Output is correct
11	Correct	315 ms	81124 KB	Output is correct
12	Correct	384 ms	81124 KB	Output is correct
13	Correct	375 ms	81124 KB	Output is correct
14	Correct	316 ms	81124 KB	Output is correct
15	Correct	335 ms	81124 KB	Output is correct
16	Correct	392 ms	81540 KB	Output is correct
17	Correct	387 ms	81920 KB	Output is correct
18	Correct	382 ms	82168 KB	Output is correct
19	Correct	350 ms	82432 KB	Output is correct
20	Correct	346 ms	82716 KB	Output is correct

Subtask #5
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	404 ms	80860 KB	Output is correct
2	Correct	337 ms	80860 KB	Output is correct
3	Correct	346 ms	80860 KB	Output is correct
4	Correct	291 ms	80860 KB	Output is correct
5	Correct	316 ms	80860 KB	Output is correct
6	Correct	431 ms	80860 KB	Output is correct
7	Correct	478 ms	80860 KB	Output is correct
8	Correct	303 ms	80860 KB	Output is correct
9	Correct	382 ms	81124 KB	Output is correct
10	Correct	336 ms	81124 KB	Output is correct
11	Correct	315 ms	81124 KB	Output is correct
12	Correct	384 ms	81124 KB	Output is correct
13	Correct	375 ms	81124 KB	Output is correct
14	Correct	316 ms	81124 KB	Output is correct
15	Correct	335 ms	81124 KB	Output is correct
16	Correct	392 ms	81540 KB	Output is correct
17	Correct	387 ms	81920 KB	Output is correct
18	Correct	382 ms	82168 KB	Output is correct
19	Correct	350 ms	82432 KB	Output is correct
20	Correct	346 ms	82716 KB	Output is correct
21	Correct	457 ms	85184 KB	Output is correct
22	Correct	497 ms	86460 KB	Output is correct
23	Correct	434 ms	87620 KB	Output is correct
24	Correct	374 ms	89036 KB	Output is correct
25	Correct	334 ms	90160 KB	Output is correct

답안 #56899

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