oj.uz

답안 #83755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83755 2018-11-10T11:04:21 Z popovicirobert 중앙값 배열 (balkan11_medians) C++14
5 / 100
 32 ms 6056 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

int arr[MAXN + 1];
pair <int, int> sol[MAXN + 1];
bool vis[MAXN + 1];

bool cmp1(const int &a, const int &b) {
    return sol[a].first > sol[b].first;
}

bool cmp2(const int &a, const int &b) {
    return sol[a].second < sol[b].second;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
        sol[i] = {1, 2 * n - 1};
    }
    sol[1] = {arr[1], arr[1]};
    vis[arr[1]] = 1;
    vector <int> ord1, ord2;
    char flag = 0;
    int p = 2;
    for(i = 2; i <= n; i++) {
        if(arr[i] > arr[i - 1]) {
            if(flag) {
                sol[p].first = sol[p + 1].first = arr[i] + 1;
                ord1.push_back(p);
                ord1.push_back(p + 1);
            }
            else { // flag == 0
                sol[p] = {arr[i], arr[i]};
                vis[arr[i]] = 1;
                sol[p + 1].first = arr[i] + 1;
            }
            flag |= 2;
        }
        if(arr[i] < arr[i - 1]) {
            if(flag) {
                sol[p].second = sol[p + 1].second = arr[i] - 1;
                ord2.push_back(p);
                ord2.push_back(p + 1);
            }
            else { // flag == 0
                sol[p] = {arr[i], arr[i]};
                vis[arr[i]] = 1;
                sol[p + 1].second = arr[i] - 1;
            }
            flag |= 1;
        }
        if(arr[i] == arr[i - 1]) {
            sol[p].first = arr[i] + 1;
            sol[p + 1].second = arr[i] - 1;
            flag = 3;
            ord1.push_back(p);
            ord2.push_back(p + 1);
        }
        p += 2;
    }
    sort(ord1.begin(), ord1.end(), cmp1);
    sort(ord2.begin(), ord2.end(), cmp2);
    int val = 2 * n - 1;
    for(auto it : ord1) {
        while(vis[val] == 1) {
            val--;
        }
        vis[val] = 1;
        sol[it].first = val;
    }
    val = 1;
    for(auto it : ord2) {
        while(vis[val] == 1) {
            val++;
        }
        vis[val] = 1;
        sol[it].first = val;
    }
    for(i = 1; i < 2 * n; i++) {
        cout << sol[i].first << " ";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
5.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Not a permutation
3 Incorrect 2 ms 516 KB Not a permutation
4 Incorrect 2 ms 516 KB Output isn't correct
5 Incorrect 2 ms 544 KB Not a permutation
6 Incorrect 2 ms 736 KB Not a permutation
7 Incorrect 2 ms 736 KB Output isn't correct
8 Incorrect 2 ms 736 KB Not a permutation
9 Incorrect 2 ms 736 KB Not a permutation
10 Incorrect 3 ms 768 KB Not a permutation
11 Incorrect 2 ms 772 KB Output isn't correct
12 Incorrect 4 ms 772 KB Not a permutation
13 Incorrect 2 ms 772 KB Not a permutation

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 832 KB Not a permutation
2 Incorrect 4 ms 860 KB Output isn't correct
3 Incorrect 6 ms 1152 KB Not a permutation
4 Incorrect 9 ms 1576 KB Not a permutation
5 Incorrect 17 ms 2568 KB Output isn't correct
6 Incorrect 32 ms 4176 KB Integer 16900548 violates the range [1, 127999]
7 Runtime error 24 ms 6056 KB Execution killed with signal 11 (could be triggered by violating memory limits)