oj.uz

Submission #786797

# Submission time Handle Problem Language Result Execution time Memory
786797 2023-07-18T12:52:51 Z SteGG Swap (BOI16_swap) C++17
100 / 100
 542 ms 14272 KB 
//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)

template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
	output << "(" << A.first << ", " << A.second <<  ")";
	return output;
}

template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
	int n = arr.size();
	output << "[";
	for(int i = 0; i < n; i++){
		output << arr[i];
		if(i != n - 1) output << ", ";
	}
	output << "]";
	return output;
}

template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
	output << "{";
	for(auto it = s.begin(); it != s.end(); it++){
		if(it != s.begin()) output << ", ";
		output << (*it);
	}
	output << "}";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
	output << "{";
	for(auto it = m.begin(); it != m.end(); it++){
		if(it != m.begin()) output << ", ";
		output << "(" << it->first << " : " << it->second << ")";
	}
	output << "}";
	return output;
}

template<class TH>
void _dbg(const char *sdbg, TH h){
	cout << sdbg << " = " << h << endl;
}

template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg != ',')cout << *sdbg++;
	cout << " = " << h << "\n";
	_dbg(sdbg+1, a...);
}

template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
	cout << '[' << index << "] = " << arr[index] << endl;
}

template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
	cout << '[' << index << ']';
	_dbg_arr(arr[index], args...);
}

//open file
#define taskname "" //name input and output file

#ifdef SteGG
void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
}
#else
void open(){
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}
#endif

//initialize
#define testcase \
	long long test; \
	cin >> test; \
	for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()

const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 2e5 + 5;
//const int base = ;
int n;
int a[maxn];
int result[maxn];
map<pair<int, int>, int> memo;

//others struct or class

struct Node{
	int index, val;
	Node *left = nullptr, *right = nullptr;
	Node(){}

	int get_min(){
		int result = val;
		if(left){
			result = min(result, left->val);
		}
		
		if(right){
			result = min(result, right->val);
		}

		return result;
	}

	~Node(){
		delete left;
		delete right;
	}
};

//others function

void dfs1(Node *cur){
	int cur_index = cur->index;

	int left_index = cur_index * 2;
	int right_index = cur_index * 2 + 1;

	if(left_index <= n){
		cur->left = new Node();
		cur->left->val = a[left_index];
		cur->left->index = left_index;
		dfs1(cur->left);
	}

	if(right_index <= n){
		cur->right = new Node();
		cur->right->val = a[right_index];
		cur->right->index = right_index;
		dfs1(cur->right);
	}
}

int depth(Node *cur, int val){ // max depth a val can come to in a subtree root cur
	if(cur->left == nullptr) return cur->index;
	if(cur->right == nullptr){
		if(val < cur->left->val) return cur->index;
		else return depth(cur->left, val);
	}

	if(val < min(cur->left->val, cur->right->val)) return cur->index;
	else if(min(cur->left->val, cur->right->val) == cur->left->val){
		return depth(cur->left, val);
	}

	int d1 = depth(cur->left, min(val, cur->left->val));
	int d2 = depth(cur->right, min(val, cur->left->val));
	if(d1 < d2){
		if(cur->left->val > val) return d1;
	}else if(cur->left->val < val) return depth(cur->left, val);

	if(cur->left->val > val) return d2;
	else return depth(cur->right, val);
}

void solve(Node *cur){
	if(cur == nullptr) return;
	if(cur->get_min() == cur->val){
		solve(cur->left);
		solve(cur->right);
	}else if(cur->get_min() == cur->left->val){
		swap(cur->val, cur->left->val);
		solve(cur->left);
		solve(cur->right);
	}else{
		swap(cur->val, cur->right->val);
		int d1 = depth(cur->left, min(cur->left->val, cur->right->val));
		int d2 = depth(cur->right, min(cur->left->val, cur->right->val));
		if(d1 < d2){
			if(cur->left->val > cur->right->val) {
				swap(cur->left->val, cur->right->val);
			}
		}else if(cur->left->val < cur->right->val){
			swap(cur->left->val, cur->right->val);
		}

		solve(cur->left);
		solve(cur->right);
	}

	result[cur->index] = cur->val;
}

//others init

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	open();
	// process input

	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}

	// build binary tree
	// consider a basic subtree with 3 node : root, left, right
	// if val of root is min -> dfs to left and right
	// else if left is min -> swap val with root and continue to dfs
	// else if right is min -> there are 2 cases
	// use dp to handle

	Node *root = new Node();
	root->index = 1;
	root->val = a[1];

	dfs1(root);

	solve(root);

	for(int i = 1; i <= n; i++){
		cout << result[i];
		if(i != n) cout << " ";
		else cout << endl;
	}

	return 0;
}

Compilation message

swap.cpp: In function 'void open()':
swap.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 9 ms 3796 KB Output is correct
17 Correct 14 ms 3828 KB Output is correct
18 Correct 9 ms 3796 KB Output is correct
19 Correct 64 ms 3848 KB Output is correct
20 Correct 62 ms 3832 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 9 ms 3796 KB Output is correct
17 Correct 14 ms 3828 KB Output is correct
18 Correct 9 ms 3796 KB Output is correct
19 Correct 64 ms 3848 KB Output is correct
20 Correct 62 ms 3832 KB Output is correct
21 Correct 36 ms 14248 KB Output is correct
22 Correct 42 ms 14272 KB Output is correct
23 Correct 36 ms 14152 KB Output is correct
24 Correct 542 ms 14208 KB Output is correct
25 Correct 531 ms 14248 KB Output is correct