Submission #1276928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276928		dqa	medians (balkan11_medians)	C++20	65 / 100	2 ms	572 KiB

medians

#include <iostream>  
#include <vector>   
#include <queue>
#include <algorithm>
#include <numeric>
#include <map>
#include <sstream>
#include <cstring>
#include <stack>
#include <climits>

using namespace std;

const long long INF = 1e9;

int n;
int b[2005];
vector<int> a;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("cowtip.in", "r", stdin); 
    // freopen("cowtip.out", "w", stdout);

    int n; cin >> n;
    bool used[2005];
    memset(used, false, sizeof(used));
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    int m = 2*n - 1;
    int num = 1;

    for (int i = 1; i <= n; i++) {
        bool check = false;
        int higher = 0, lower = 0;
        int elements = 2 * i - 1;
        for(int x : a) {
            if (x > b[i]) {
                higher++;
            } else if (x < b[i]) {
                lower++;
            }
        }
        if(!used[b[i]]) {
            a.push_back(b[i]);
            used[b[i]] = true;
        }
        while((int)a.size() != elements) {
            if(lower > higher) {
                while(m > 0 && used[m]) {
                    m--;
                }
                a.push_back(m);
                used[m] = true;
                higher++;
            } else if (lower < higher) {
                while(num <= m && used[num]) {
                    num++;
                }
                a.push_back(num);
                used[num] = true;
                lower++;
            } else if (lower == higher) {
                while(m > 0 && used[m]) {
                    m--;
                }
                a.push_back(m);
                used[m] = true;
                higher++;
            
                while(num <= m && used[num]) {
                    num++;
                }
                a.push_back(num);
                used[num] = true;
                lower++;
            }
        }
    }
    for (auto v : a) {
            cout << v << " ";
        }
        cout << "\n";
    return 0;
}

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