oj.uz

Submission #391919

# Submission time Handle Problem Language Result Execution time Memory
391919 2021-04-20T07:32:50 Z AmShZ Swap (BOI16_swap) C++11
68 / 100
 1000 ms 39212 KB 
// khodaya khodet komak kon
// Maybe on the Moon
# include <bits/stdc++.h>
# pragma GCC target("avx2")

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e5 + 10;
const int xm = 18;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;

int n, b[xm][xn];
vector <int> vec[xn];

void solve(int id, int h){
	if ((lc) > n)
		return;
	bool fl = false;
	if (b[h][lc] < b[h][id])
		swap(b[h][lc], b[h][id]);
	if ((rc) > n)
		return;
	if (b[h][rc] < b[h][id])
		swap(b[h][rc], b[h][id]), fl = true;
	if (!fl){
		for (int v : vec[id])
			b[h + 1][v] = b[h][v];
		solve(lc, h + 1), solve(rc, h + 1);
		for (int v : vec[id])
			b[h][v] = b[h + 1][v];
		return;
	}
	int mn = min(b[h][lc], b[h][rc]);
	int mx = max(b[h][lc], b[h][rc]);
	for (int v : vec[id])
		b[h + 1][v] = b[h][v];
	b[h + 1][lc] = b[h + 1][rc] = mn;
	solve(lc, h + 1), solve(rc, h + 1);
	int x, y;
	for (int v : vec[lc])
		if (b[h + 1][v] == mn)
			x = v;
	for (int v : vec[rc])
		if (b[h + 1][v] == mn)
			y = v;
	if (y < x){
		b[h][lc] = mx;
		for (int v : vec[lc])
			b[h + 1][v] = b[h][v];
		b[h + 1][id] = b[h][id];
		solve(lc, h + 1);
		for (int v : vec[id])
			b[h][v] = b[h + 1][v];
	}
	else{
		b[h][rc] = mx;
		for (int v : vec[rc])
			b[h + 1][v] = b[h][v];
		b[h + 1][id] = b[h][id];
		solve(rc, h + 1);
		for (int v : vec[id])
			b[h][v] = b[h + 1][v];
	}
}


int main(){
	InTheNameOfGod;

	cin >> n;
	for (int i = 1; i <= n; ++ i){
		cin >> b[0][i];
		int v = i;
		while (v)
			vec[v].push_back(i), v /= 2;
	}
	solve(1, 0);
	for (int i = 1; i <= n; ++ i)
		cout << b[0][i] << sep;
	cout << endl;

	return 0;
}

Compilation message

swap.cpp: In function 'void solve(int, int)':
swap.cpp:71:2: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |  if (y < x){
      |  ^~
swap.cpp:71:2: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 5 ms 5068 KB Output is correct
13 Correct 4 ms 5148 KB Output is correct
14 Correct 4 ms 5148 KB Output is correct
15 Correct 4 ms 5060 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 5 ms 5068 KB Output is correct
13 Correct 4 ms 5148 KB Output is correct
14 Correct 4 ms 5148 KB Output is correct
15 Correct 4 ms 5060 KB Output is correct
16 Correct 49 ms 12708 KB Output is correct
17 Correct 47 ms 12712 KB Output is correct
18 Correct 51 ms 12824 KB Output is correct
19 Correct 412 ms 12732 KB Output is correct
20 Correct 404 ms 12852 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5052 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 5 ms 5068 KB Output is correct
13 Correct 4 ms 5148 KB Output is correct
14 Correct 4 ms 5148 KB Output is correct
15 Correct 4 ms 5060 KB Output is correct
16 Correct 49 ms 12708 KB Output is correct
17 Correct 47 ms 12712 KB Output is correct
18 Correct 51 ms 12824 KB Output is correct
19 Correct 412 ms 12732 KB Output is correct
20 Correct 404 ms 12852 KB Output is correct
21 Correct 245 ms 39144 KB Output is correct
22 Correct 234 ms 39120 KB Output is correct
23 Correct 242 ms 39212 KB Output is correct
24 Execution timed out 1091 ms 34268 KB Time limit exceeded
25 Halted 0 ms 0 KB -