Submission #117154

#	Time	Username	Problem	Language	Result	Execution time	Memory
117154		Just_Solve_The_Problem	Swap (BOI16_swap)	C++11	100 / 100	202 ms	16168 KiB

swap

#include <bits/stdc++.h>

#define ll long long
#define ok puts("ok");

using namespace std;

const int N = (int)2e5 + 7;

int n;
int a[N];
map <pair<int, int>, int> mp;

int get(int ind, int y) {
	if (mp.count({ind, y})) return mp[{ind, y}];
	if (ind * 2 > n) return ind;
	if (ind * 2 + 1 > n) {
		if (y > a[ind * 2]) {
			return ind * 2;
		}
		return ind;
	}
	if (y < min(a[ind * 2], a[ind * 2 + 1])) {
		return ind;
	} else if (a[ind * 2] < min(y, a[ind * 2 + 1])) {
		return mp[{ind, y}] = get(ind * 2, y);
	} else {
		int mn = min(y, a[ind * 2]);
		int mx = max(y, a[ind * 2]);
		if (get(ind * 2, mn) < get(ind * 2 + 1, mn)) {
			if (y == mn) return mp[{ind, y}] = get(ind * 2, y);
			return mp[{ind, y}] = get(ind * 2 + 1, y);
		} else {
			if (y == mn) return mp[{ind, y}] = get(ind * 2 + 1, y);
			return mp[{ind, y}] = get(ind * 2, y);
		}
	}
}

void solve(int ind) {
	if (ind * 2 > n) return ;
	if (ind * 2 + 1 > n) {
		if (a[ind] > a[ind * 2]) {
			swap(a[ind], a[ind * 2]);
		}
		return ;
	}
	if (a[ind] < min(a[ind * 2], a[ind * 2 + 1])) {
		
	} else if (a[ind * 2] < min(a[ind], a[ind * 2 + 1])) {
		swap(a[ind * 2], a[ind]);
	} else {
		int mn = min(a[ind], a[ind * 2]);
		int mx = max(a[ind], a[ind * 2]);
		a[ind] = a[ind * 2 + 1];
		if (get(ind * 2, mn) < get(ind * 2 + 1, mn)) {
			a[ind * 2] = mn;
			a[ind * 2 + 1] = mx;
		} else {
			a[ind * 2] = mx;
			a[ind * 2 + 1] = mn;
		}
	}
	solve(ind + 1);
}

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	solve(1);
	for (int i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
}

Compilation message (stderr)

swap.cpp: In function 'int get(int, int)':
swap.cpp:29:7: warning: unused variable 'mx' [-Wunused-variable]
   int mx = max(y, a[ind * 2]);
       ^~
swap.cpp: At global scope:
swap.cpp:67:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
swap.cpp: In function 'int main()':
swap.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32