oj.uz

답안 #336037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336037 2020-12-14T14:20:36 Z Dymo 중앙값 배열 (balkan11_medians) C++14
100 / 100
 34 ms 4964 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb    push_back
#define eb   emplace_back
#define ll   long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define ld long double
#define ull  long long
#define endl "\n"
const ll maxn=7e5+10;
const ll mod =978123409 ;
const long double pi=3.14159265359;


ll a[maxn];
bool dd[maxn];
vector<ll> ans;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
     cin>>n ;
     for (int i=1;i<=n;i++)
     {
         cin>>a[i];
     }
     dd[a[1]]=1;
     ans.pb(a[1]);
     ll st=1;
     ll ed=2*n-1;
     for (int i=2;i<=n;i++)
     {
         while (dd[st]&&st<=2*n-1) st++;
         while (dd[ed]&&ed>=1) ed--;
        if (a[i]==a[i-1])
        {
            dd[st]=1;
            dd[ed]=1;
            ans.pb(ed);
            ans.pb(st);
            ed--;
            st++;
        }
        else if (a[i]>a[i-1])
        {
            if (dd[a[i]])
            {
               dd[ed]=1;
               ans.pb(ed);
               ed--;
               while (dd[ed]&&ed>=1) ed--;
               ans.pb(ed);
               dd[ed]=1;
               ed--;
            }
            else
            {
                ans.pb(a[i]);
                dd[a[i]]=1;
                ans.pb(ed);
                dd[ed]=1;
                ed--;
            }
        }
        else
        {
             if (dd[a[i]])
            {
               ans.pb(st);
               dd[st]=1;
               st++;
               while (dd[st]&&st<=2*n-1) st++;
               ans.pb(st);
               dd[st]=1;
               st++;
            }
            else
            {
                ans.pb(a[i]);
                dd[a[i]]=1;
                ans.pb(st);
                dd[st]=1;
                st++;
            }
        }
     }
     for (auto to:ans) cout <<to<<" ";

}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
medians.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   29 |         freopen("test.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 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 6 ms 1136 KB Output is correct
5 Correct 11 ms 1900 KB Output is correct
6 Correct 21 ms 3304 KB Output is correct
7 Correct 34 ms 4964 KB Output is correct