# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
330764 | BeanZ | medians (balkan11_medians) | C++14 | 1091 ms | 2168 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 2e5 + 5;
const int lg = 60;
const int mod = 998244353;
const long long oo = 1e18;
const int lim = 1e6 + 5;
long double eps = 1e-3;
ll vis[N], b[N], a[N];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
b[1] = a[1];
vis[b[1]] = 1;
for (int i = 2; i <= n; i++){
if (vis[a[i]] == 0){
b[i * 2 - 2] = a[i];
vis[a[i]] = 1;
ll gr = 0, sm = 0;
for (int j = 1; j <= (i * 2 - 2); j++){
if (b[j] < a[i]) sm++;
if (b[j] > a[i]) gr++;
}
if (sm > gr){
for (int j = 2 * n - 1; j >= 1; j--){
if (vis[j]) continue;
b[i * 2 - 1] = j;
vis[j] = 1;
break;
}
} else {
for (int j = 1; j <= (2 * n + 1); j++){
if (vis[j]) continue;
b[i * 2 - 1] = j;
vis[j] = 1;
break;
}
}
} else {
ll gr = 0, sm = 0;
for (int j = 1; j < (i * 2 - 2); j++){
if (b[j] < a[i]) sm++;
if (b[j] > a[i]) gr++;
}
if (sm > gr){
ll cnt = 2;
for (int j = 2 * n - 1; j >= 1; j--){
if (vis[j]) continue;
if (cnt == 0) break;
b[i * 2 - cnt] = j;
vis[j] = 1;
cnt--;
}
} else if (gr > sm) {
ll cnt = 2;
for (int j = 1; j <= (2 * n - 1); j++){
if (vis[j]) continue;
if (cnt == 0) break;
b[i * 2 - cnt] = j;
vis[j] = 1;
cnt--;
}
} else {
ll cnt = 2;
for (int j = 1; j <= (2 * n - 1); j++){
if (vis[j]) continue;
if (cnt == 1) break;
b[i * 2 - cnt] = j;
vis[j] = 1;
cnt--;
}
for (int j = 2 * n - 1; j >= 1; j--){
if (vis[j]) continue;
if (cnt == 0) break;
b[i * 2 - cnt] = j;
vis[j] = 1;
cnt--;
}
}
}
}
for (int i = 1; i <= (2 * n - 1); i++) cout << b[i] << " ";
}
/*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |