| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258584 |
2020-08-06T07:38:14 Z |
임성재(#5051) |
Swap (BOI16_swap) |
C++17 |
|
0 ms |
384 KB |
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
int n;
int a[800010];
int ans[800010];
int f(int x) {
if(x*2 > n || a[x] < a[x*2] && a[x] < a[x*2+1]) return x;
if(x*2+1 > n || a[x*2] < a[x] && a[x*2] < a[x*2+1]) {
swap(a[x], a[x*2]);
int ret = f(x*2);
swap(a[x], a[x*2]);
return ret;
}
swap(a[x], a[x*2+1]);
int p, q;
if(a[x*2] < a[x*2+1]) p = f(x * 2);
else q = f(x * 2 + 1);
swap(a[x*2], a[x*2+1]);
if(a[x*2] < a[x*2+1]) p = f(x * 2);
else q = f(x * 2 + 1);
swap(a[x*2], a[x*2+1]);
swap(a[x], a[x*2+1]);
return min(p, q);
}
void g(int x) {
if(x*2 > n) return;
if(x*2+1 > n) {
if(a[x*2] < a[x*2+1]) swap(a[x], a[x*2]);
return;
}
if(a[x*2] < a[x] && a[x*2] < a[x*2+1]) {
swap(a[x], a[x*2]);
}
else if(a[x*2+1] < a[x] && a[x*2+1] < a[x*2]) {
swap(a[x], a[x*2+1]);
int p, q;
if(a[x*2] < a[x*2+1]) p = f(x * 2);
else q = f(x * 2 + 1);
swap(a[x*2], a[x*2+1]);
if(a[x*2] < a[x*2+1]) p = f(x * 2);
else q = f(x * 2 + 1);
if(p < q) {
if(a[x*2] > a[x*2+1]) swap(a[x*2], a[x*2+1]);
}
else {
if(a[x*2] < a[x*2+1]) swap(a[x*2], a[x*2+1]);
}
}
g(x*2);
g(x*2+1);
}
int main() {
fast;
cin >> n;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
g(1);
for(int i=1; i<=n; i++) {
cout << a[i] << " ";
}
}
Compilation message
swap.cpp: In function 'int f(int)':
swap.cpp:25:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(x*2 > n || a[x] < a[x*2] && a[x] < a[x*2+1]) return x;
~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
swap.cpp:26:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(x*2+1 > n || a[x*2] < a[x] && a[x*2] < a[x*2+1]) {
~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
swap.cpp:37:9: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
int p, q;
^
swap.cpp:37:6: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
int p, q;
^
swap.cpp: In function 'void g(int)':
swap.cpp:75:3: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(p < q) {
^~
swap.cpp:75:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
