| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 258589 |
2020-08-06T07:48:12 Z |
임성재(#5051) |
Swap (BOI16_swap) |
C++17 |
|
4 ms |
3456 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(a[x] < a[x*2] && a[x] < a[x*2+1]) return x;
if(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 > n) return;
if(x*2 <= n && a[x*2] < a[x] && a[x*2] < a[x*2+1]) {
swap(a[x], a[x*2]);
}
else if(x*2+1 <= n && 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<=800000; i++) {
a[i] = inf;
}
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: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:71:3: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(p < q) {
^~
swap.cpp:71:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3456 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3456 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3456 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3456 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3456 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
