oj.uz

답안 #499578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499578 2021-12-28T20:21:50 Z colossal_pepe 중앙값 배열 (balkan11_medians) C++17
100 / 100
 25 ms 3024 KB 
#include <iostream>
#include <vector>
using namespace std;

#define upd while(mark[left]) left++; while(mark[right]) right--

int n, b[100005];
bool mark[2 * 100005];
vector<int> ans;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    mark[0] = mark[2 * n] = 1;
    int left = 0, right = 2 * n;
    ans.push_back(b[0]);
    mark[b[0]] = 1;
    for (int i = 1; i < n; i++) {
        upd;
        if (b[i - 1] < b[i]) {
            ans.push_back(right);
            mark[right] = 1;
            if (mark[b[i]]) {
                upd;
                ans.push_back(right);
                mark[right] = 1;
            } else {
                ans.push_back(b[i]);
                mark[b[i]] = 1;
            }
        } else if (b[i - 1] > b[i]) {
            ans.push_back(left);
            mark[left] = 1;
            if (mark[b[i]]) {
                upd;
                ans.push_back(left);
                mark[left] = 1;
            } else {
                ans.push_back(b[i]);
                mark[b[i]] = 1;
            }
        } else {
            ans.push_back(left), ans.push_back(right);
            mark[left] = mark[right] = 1;
        }
    }
    for (int i : ans) {
        cout << i << ' ';
    }
    cout << endl;
    return 0;
}

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 8 ms 1232 KB Output is correct
6 Correct 15 ms 2124 KB Output is correct
7 Correct 25 ms 3024 KB Output is correct