oj.uz

Submission #56899

# Submission time Handle Problem Language Result Execution time Memory
56899 2018-07-13T06:30:17 Z ainta Swap (BOI16_swap) C++17
100 / 100
 497 ms 90160 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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