oj.uz

답안 #231497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231497 2020-05-13T20:02:21 Z summitwei 중앙값 배열 (balkan11_medians) C++17
100 / 100
 71 ms 3820 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long double ld;

#define F0R(i, a) for(int i=0; i<a; i++)
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define RFOR(i, b, a) for(int i=b; i>=a; i--)

#define f first
#define s second
#define pb push_back
#define INF 0x3f3f3f3f
#define MOD 998244353LL

#define MN 200005
int n;
int b[MN];
vi a;
bool used[MN];

int main(){
    cin >> n;
    FOR(i, 1, n){
        cin >> b[i];
    }
    used[b[1]] = true;
    a.pb(b[1]);
    int l=1, r=2*n-1;
    FOR(i, 2, n){
        if(b[i] == b[i-1]){
            while(used[l]) ++l;
            while(used[r]) --r;
            a.pb(l);
            a.pb(r);
            used[l] = used[r] = true;
        } else if(b[i] < b[i-1]){
            if(used[b[i]]){
                while(used[l]) ++l;
                a.pb(l); used[l] = true;
                while(used[l]) ++l;
                a.pb(l); used[l] = true;
            } else{
                a.pb(b[i]);
                used[b[i]] = true;
                while(used[l]) ++l;
                a.pb(l); used[l] = true;
            }
        } else{
            if(used[b[i]]){
                while(used[r]) --r;
                a.pb(r); used[r] = true;
                while(used[r]) --r;
                a.pb(r); used[r] = true;
            } else{
                a.pb(b[i]);
                used[b[i]] = true;
                while(used[r]) --r;
                a.pb(r); used[r] = true;
            }
        }
    }
    for(auto u : a) cout << u << " ";
    cout << "\n";

    return 0;
}

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 14 ms 1024 KB Output is correct
5 Correct 25 ms 1532 KB Output is correct
6 Correct 45 ms 2544 KB Output is correct
7 Correct 71 ms 3820 KB Output is correct