oj.uz

Submission #786773

# Submission time Handle Problem Language Result Execution time Memory
786773 2023-07-18T12:44:02 Z vjudge1 Swap (BOI16_swap) C++17
100 / 100
 536 ms 15452 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 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 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 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 332 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 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 332 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 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 9 ms 3964 KB Output is correct
17 Correct 10 ms 3932 KB Output is correct
18 Correct 9 ms 3924 KB Output is correct
19 Correct 65 ms 3996 KB Output is correct
20 Correct 64 ms 3916 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 332 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 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 9 ms 3964 KB Output is correct
17 Correct 10 ms 3932 KB Output is correct
18 Correct 9 ms 3924 KB Output is correct
19 Correct 65 ms 3996 KB Output is correct
20 Correct 64 ms 3916 KB Output is correct
21 Correct 37 ms 15312 KB Output is correct
22 Correct 36 ms 15308 KB Output is correct
23 Correct 35 ms 15268 KB Output is correct
24 Correct 536 ms 15296 KB Output is correct
25 Correct 536 ms 15452 KB Output is correct