Submission #1178468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178468		_dtq_	medians (balkan11_medians)	C++17	100 / 100	58 ms	14664 KiB

medians

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (long long)(x.size())
using namespace std;

const ll N = 3e5 + 9;

ll n, i, a[N], b[N], bit[N];

bool check[N];

void up( ll x )
{
    while(x <= 2 * n - 1)
    {
        bit[x] ++;

        x += (x & (-x));
    }
}

ll get( ll x )
{
    ll sum = 0;

    while(x > 0)
    {
        sum += bit[x];

        x -= (x & (-x));
    }

    return sum;
}

int main()
{

#define TN "medians"

    if(fopen(TN ".in", "r"))
    {
        freopen(TN ".in", "r", stdin);
        freopen(TN ".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    for( i = 1; i <= n; i ++ ) cin >> b[i];

    a[1] = b[1];

    check[b[1]] = 1;

    up(b[1]);

    set<ll>ans;

    for( i = 2; i <= n; i ++ )
    {
        if(check[b[i]])  continue;

        check[b[i]] = 1;

        a[2 * i - 1] = b[i];
    }

    for( i = 1; i <= 2 * n - 1; i ++ )
        if(check[i] == 0) ans.insert(i);

    ll vt = 2;

    for( i = 2; i <= n; i ++ )
    {
        while(vt <= 2 * i - 1)
        {
            if(a[vt])
            {
                up(a[vt]);

                vt ++;

                continue;
            }

            ll res1 = get(b[i] - 1);

            ll res2 = get(2 * n - 1) - get(b[i]);

            if(res1 < res2)
            {
                a[vt] = *ans.begin();

                ans.erase(ans.begin());
            }
            else
            {
                a[vt] = *ans.rbegin();

                ans.erase(--ans.end());
            }

            up(a[vt]);

            vt ++;
        }
    }

    for( i = 1; i <= 2 * n - 1; i ++ ) cout << a[i] << " ";

    return 0;
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(TN ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
medians.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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