제출 #786797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786797		SteGG	Swap (BOI16_swap)	C++17	100 / 100	542 ms	14272 KiB

swap

//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;
}

컴파일 시 표준 에러 (stderr) 메시지

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