oj.uz

답안 #372447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372447 2021-02-28T08:20:38 Z Killer2501 중앙값 배열 (balkan11_medians) C++14
100 / 100
 103 ms 11884 KB 
#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "media"
#define pll pair<ll, ll>
#define pii pair< pll, ll >
#define fi first
#define se second

using namespace std;
using ll = long long ;
using ull = unsigned long long;
const int N = 3e5+5;
const ll mod = 1e9+7;
const ll base1 = 1313;
const ll base2 = 3113;
ll m, n, k, t, T, ans, a[N], b[N], c[N], lab[N], tong, cur;
vector<ll> kq;
set<ll> st;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> b[i];
    kq.pb(b[1]);
    for(int i = 1; i <= n*2-1; i ++)st.insert(i);
    st.erase(b[1]);
    for(int i = 2; i <= n; i ++)
    {
        if(st.find(b[i]) != st.end())
        {
            kq.pb(b[i]);
            st.erase(b[i]);
            if(b[i] > b[i-1])
            {
                kq.pb(*st.rbegin());
                st.erase(*st.rbegin());
            }
            else
            {
                kq.pb(*st.begin());
                st.erase(*st.begin());
            }
        }
        else
        {
            if(b[i] == b[i-1])
            {
                kq.pb(*st.begin());
                st.erase(*st.begin());
                kq.pb(*st.rbegin());
                st.erase(*st.rbegin());
            }
            else if(b[i] < b[i-1])
            {
                kq.pb(*st.begin());
                st.erase(*st.begin());
                kq.pb(*st.begin());
                st.erase(*st.begin());
            }
            else
            {
                kq.pb(*st.rbegin());
                st.erase(*st.rbegin());
                kq.pb(*st.rbegin());
                st.erase(*st.rbegin());
            }
        }
    }
    for(ll x : kq)cout << x <<" ";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".in", "r"))
    {
		freopen(task".in","r",stdin);
		freopen(task".out","w",stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    for(int tt = 1; tt <= ntest; tt ++)
    sol();
}

Compilation message

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

Subtask #1
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 15 ms 2176 KB Output is correct
5 Correct 31 ms 4076 KB Output is correct
6 Correct 66 ms 7788 KB Output is correct
7 Correct 103 ms 11884 KB Output is correct