답안 #267991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
267991 2020-08-16T07:43:52 Z stefantaga 중앙값 배열 (balkan11_medians) C++14
100 / 100
83 ms 3576 KB
#include<bits/stdc++.h>
#define DIM 200005
using namespace std;
int n,i,p,u;
int v[DIM],frec[DIM],sol[DIM];
int main()
{

    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    sol[1]=v[1];
    frec[v[1]]=1;
    p=1;
    u=2*n-1;
    for(i=2; i<=n; i++)
    {
        while(frec[p]==1)
        {
            p++;
        }
        while(frec[u]==1)
        {
            u--;
        }
        if(v[i]==v[i-1])
        {
            sol[2*i-2]=p;
            sol[2*i-1]=u;
            frec[p]=frec[u]=1;
        }
        else
        {
            if(frec[v[i]]==0)
            {
                sol[2*i-2]=v[i];
                frec[v[i]]=1;
                if(v[i]>v[i-1])
                {
                    sol[2*i-1]=u;
                    frec[u]=1;
                }
                else
                {
                    sol[2*i-1]=p;
                    frec[p]=1;
                }
            }
            else
            {
                if(v[i]>v[i-1])
                {
                    sol[2*i-2]=u;
                    frec[u]=1;
                    while(frec[u]==1)
                    {
                        u--;
                    }
                    sol[2*i-1]=u;
                    frec[u]=1;
                }
                else
                {
                    sol[2*i-2]=p;
                    frec[p]=1;
                    while(frec[p]==1)
                    {
                        p++;
                    }
                    sol[2*i-1]=p;
                    frec[p]=1;
                }
            }
        }
    }
    for(i=1; i<=2*n-1; i++)
    {
        cout<<sol[i]<<" ";
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 13 ms 768 KB Output is correct
5 Correct 25 ms 1400 KB Output is correct
6 Correct 50 ms 2428 KB Output is correct
7 Correct 83 ms 3576 KB Output is correct