oj.uz

답안 #785786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785786 2023-07-17T15:25:34 Z vjudge1 Swap (BOI16_swap) C++17
0 / 100
 1 ms 328 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];

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

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);
		if(cur->left->get_min() != cur->left->val && cur->right->get_min() != cur->right->val){
			if(cur->left->val > cur->right->val){
				swap(cur->left->val, cur->right->val);
			}
		}else if(cur->left->val != cur->left->get_min()){
			if(cur->left->val > cur->right->val){
				if(cur->right->left && cur->right->right && cur->left->val > min(cur->right->left->val, cur->right->right->val)){
					swap(cur->left->val, cur->right->val);
				}else if(cur->left->get_min() > cur->right->val){
					swap(cur->left->val, cur->right->val);
				}
			}else{
				swap(cur->left->val, cur->right->val);
			}
		}else if(cur->right->get_min() != cur->right->val){
			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
	// if min val of subtree > val of root -> cicular swap
	// else if val of root < val of left -> cicular swap
	// else if val of root > val of left -> swap right and root

	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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -