Submission #391919

#	Time	Username	Problem	Language	Result	Execution time	Memory
391919		AmShZ	Swap (BOI16_swap)	C++11	68 / 100	1091 ms	39212 KiB

swap

// 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 (stderr)

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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 0 / 32