oj.uz

답안 #90590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90590 2018-12-22T18:03:13 Z 314rate 중앙값 배열 (balkan11_medians) C++14
5 / 100
 27 ms 4892 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N=2*100000+5;

int n;
int b[N];
int v[N];

bool viz[N];

void upd(int i,int x)
{
    v[i]=x;
    viz[x]=1;
}

int mip=1;
int mxp;

int f_mi()
{
    while(viz[mip])
    {
        mip++;
    }
    return mip;
}

int f_mx()
{
    while(viz[mxp])
    {
        mxp--;
    }
    return mxp;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //  freopen("medians.in","r",stdin);
  //  freopen("medians.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    mxp=2*n-1;
    upd(1,b[1]);
    upd(3,b[2]);
    if(b[1]<b[2])
    {
        upd(2,f_mx());
    }
    else
    {
        upd(2,f_mi());
    }
    for(int i=3;i<=n;i++)
    {
        int p=2*i-1;
        if(b[i-1]==b[i])
        {
            upd(p-1,f_mi());
            upd(p,f_mx());
        }
        if(b[i-1]<b[i])
        {
            if(viz[b[i]]==0)
            {
                upd(p,b[i]);
                upd(p-1,f_mi());
            }
            else
            {
                upd(p-1,f_mx());
                upd(p,f_mx());
            }
        }
        if(b[i-1]>b[i])
        {
            if(viz[b[i]]==0)
            {
                upd(p,b[i]);
                upd(p-1,f_mx());
            }
            else
            {
                upd(p-1,f_mi());
                upd(p,f_mi());
            }
        }
        ///if(i==5) break;
    }
    for(int i=1;i<=2*n-1;i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<"\n";
    return 0;
}
/**


1     3     3     4     5
1  ?  3  ?  ?  ?  ?  ?  ?
1  9  3  2  4  8  7  5  6


f(i) = i / 2

info (i)
:
 x;
 exista x
 f(i) < x
 f(i) > x


**/

Subtask #1
5.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Not a permutation
2 Incorrect 2 ms 604 KB Output isn't correct
3 Incorrect 2 ms 716 KB Output isn't correct
4 Incorrect 2 ms 716 KB Not a permutation
5 Incorrect 2 ms 848 KB Output isn't correct
6 Correct 2 ms 848 KB Output is correct
7 Incorrect 2 ms 864 KB Not a permutation
8 Incorrect 2 ms 972 KB Output isn't correct
9 Incorrect 2 ms 972 KB Output isn't correct
10 Incorrect 2 ms 972 KB Output isn't correct
11 Incorrect 2 ms 972 KB Not a permutation
12 Incorrect 2 ms 1028 KB Output isn't correct
13 Incorrect 2 ms 1028 KB Output isn't correct

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1028 KB Output isn't correct
2 Incorrect 3 ms 1084 KB Not a permutation
3 Incorrect 4 ms 1108 KB Output isn't correct
4 Incorrect 6 ms 1528 KB Output isn't correct
5 Incorrect 10 ms 2024 KB Not a permutation
6 Incorrect 17 ms 3236 KB Not a permutation
7 Incorrect 27 ms 4892 KB Not a permutation