Submission #1246755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246755		nguyenhuythach	medians (balkan11_medians)	C++20	100 / 100	58 ms	3772 KiB

medians

//cre: http://www.boi2011.ro/resurse/tasks/medians-sol.pdf
//problem is being solved by greedy 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> Tab(N), used(2 * N);
    vector<int> ans;
    int L = 1, R = 2 * N - 1;
    for (int i = 0; i < N; i++)
    {
        while (used[L])
            L++;
        while (used[R])
            R--;
        cin >> Tab[i];
        if (i == 0)
        {
            ans.push_back(Tab[i]);
            used[Tab[i]] = 1;
            continue;
        }
        if (Tab[i] == Tab[i - 1])
        {
            ans.push_back(L);
            ans.push_back(R);
            used[L] = used[R] = 1;
            continue;
        }
        if (Tab[i] > Tab[i - 1])
        {
            ans.push_back(R);
            used[R] = 1;
            while (used[R])
                R--;
        }
        else
        {
            ans.push_back(L);
            used[L] = 1;
            while (used[L])
                L++;
        }
        if (used[Tab[i]] == 0)
        {
            ans.push_back(Tab[i]);
            used[Tab[i]] = 1;
        }
        else
        {
            if (Tab[i] > Tab[i - 1])
                ans.push_back(R), used[R] = 1;
            else
                ans.push_back(L), used[L] = 1;
        }
    }
    for (int i = 0; i < 2 * N - 1; i++)
        cout << ans[i] << ' ';
}

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