제출 #786797

#제출 시각아이디문제언어결과실행 시간메모리
786797SteGGSwap (BOI16_swap)C++17
100 / 100
542 ms14272 KiB
//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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...