oj.uz

Submission #56897

# Submission time Handle Problem Language Result Execution time Memory
56897 2018-07-13T06:18:20 Z ainta Swap (BOI16_swap) C++17
48 / 100
 1000 ms 82264 KB 
#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

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

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

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

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

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