Submission #222626

#	Time	Username	Problem	Language	Result	Execution time	Memory
222626		Bruteforceman	중앙값 배열 (balkan11_medians)	C++11	100 / 100	123 ms	12152 KiB

medians

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector <int> b (n + 1);
    vector <bool> done (n + 1);
    set <int> s;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        if(s.count(b[i]) == 0) {
            done[i] = true;
        }
        s.insert(b[i]);
    }
    set <int> can;
    for(int i = 1; i <= 2*n - 1; i++) {
        if(!s.count(i)) {
            can.insert(i);
        }
    }
    vector <int> v;
    for(int i = n; i > 1; i--) {
        if(done[i]) {
            can.insert(b[i]);
        }
        int p, q;
        if(b[i] == b[i - 1]) {
            p = *(--can.lower_bound(b[i]));
            q = *can.upper_bound(b[i]);
        } else if (b[i] > b[i - 1]) {
            p = *can.upper_bound(b[i - 1]);
            q = *can.upper_bound(p);
        } else {
            p = *(--can.lower_bound(b[i - 1]));
            q = *(--can.lower_bound(p));
        }
        can.erase(p); can.erase(q);
        v.emplace_back(p); v.emplace_back(q);
    }
    v.emplace_back(b[1]);
    reverse(v.begin(), v.end());
    for(auto i : v) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:6:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
medians.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35