| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258612 |
2020-08-06T08:44:44 Z |
임성재(#5051) |
Swap (BOI16_swap) |
C++17 |
|
1 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(min({a[x], a[x*2], a[x*2+1]}) == a[x]) return x;
if(min({a[x], a[x*2], a[x*2+1]}) == a[x*2]) {
swap(a[x], a[x*2]);
int ret = f(x*2);
swap(a[x], a[x*2]);
return ret;
}
else {
swap(a[x], a[x*2+1]);
int p, q;
if(min(a[x*2], a[x*2+1]) == a[x*2]) p = f(x*2);
else q = f(x * 2 + 1);
swap(a[x*2], a[x*2+1]);
if(min(a[x*2], a[x*2+1]) == a[x*2]) 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(min({a[x], a[x*2], a[x*2+1]}) == a[x]);
else if(min({a[x], a[x*2], a[x*2+1]}) == a[x*2]) {
swap(a[x], a[x*2]);
}
else {
swap(a[x], a[x*2+1]);
int p, q;
if(min(a[x*2], a[x*2+1]) == a[x*2]) p = f(x*2);
else q = f(x * 2 + 1);
swap(a[x*2], a[x*2+1]);
if(min(a[x*2], a[x*2+1]) == a[x*2]) p = f(x*2);
else q = f(x * 2 + 1);
if(p < q && a[x*2] > a[x*2+1]) swap(a[x*2], a[x*2+1]);
else if(p > q && 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<=4*n; i++) {
a[i] = i;
}
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:38:10: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
int p, q;
^
swap.cpp:38:7: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
int p, q;
^
swap.cpp: In function 'void g(int)':
swap.cpp:76:8: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
else if(p > q && a[x*2] < a[x*2+1]) swap(a[x*2], a[x*2+1]);
^~
swap.cpp:76:8: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
