Submission #83755

#	Time	Username	Problem	Language	Result	Execution time	Memory
83755		popovicirobert	medians (balkan11_medians)	C++14	5 / 100	32 ms	6056 KiB

medians

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

int arr[MAXN + 1];
pair <int, int> sol[MAXN + 1];
bool vis[MAXN + 1];

bool cmp1(const int &a, const int &b) {
    return sol[a].first > sol[b].first;
}

bool cmp2(const int &a, const int &b) {
    return sol[a].second < sol[b].second;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
        sol[i] = {1, 2 * n - 1};
    }
    sol[1] = {arr[1], arr[1]};
    vis[arr[1]] = 1;
    vector <int> ord1, ord2;
    char flag = 0;
    int p = 2;
    for(i = 2; i <= n; i++) {
        if(arr[i] > arr[i - 1]) {
            if(flag) {
                sol[p].first = sol[p + 1].first = arr[i] + 1;
                ord1.push_back(p);
                ord1.push_back(p + 1);
            }
            else { // flag == 0
                sol[p] = {arr[i], arr[i]};
                vis[arr[i]] = 1;
                sol[p + 1].first = arr[i] + 1;
            }
            flag |= 2;
        }
        if(arr[i] < arr[i - 1]) {
            if(flag) {
                sol[p].second = sol[p + 1].second = arr[i] - 1;
                ord2.push_back(p);
                ord2.push_back(p + 1);
            }
            else { // flag == 0
                sol[p] = {arr[i], arr[i]};
                vis[arr[i]] = 1;
                sol[p + 1].second = arr[i] - 1;
            }
            flag |= 1;
        }
        if(arr[i] == arr[i - 1]) {
            sol[p].first = arr[i] + 1;
            sol[p + 1].second = arr[i] - 1;
            flag = 3;
            ord1.push_back(p);
            ord2.push_back(p + 1);
        }
        p += 2;
    }
    sort(ord1.begin(), ord1.end(), cmp1);
    sort(ord2.begin(), ord2.end(), cmp2);
    int val = 2 * n - 1;
    for(auto it : ord1) {
        while(vis[val] == 1) {
            val--;
        }
        vis[val] = 1;
        sol[it].first = val;
    }
    val = 1;
    for(auto it : ord2) {
        while(vis[val] == 1) {
            val++;
        }
        vis[val] = 1;
        sol[it].first = val;
    }
    for(i = 1; i < 2 * n; i++) {
        cout << sol[i].first << " ";
    }
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 5 / 65
• Subtask 2: 0 / 35