oj.uz

Submission #83761

# Submission time Handle Problem Language Result Execution time Memory
83761 2018-11-10T11:18:08 Z popovicirobert medians (balkan11_medians) C++14
100 / 100
 33 ms 4344 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], sol[2 * MAXN + 1];
bool vis[2 * MAXN + 1];

inline int get_max(int &b) {
    while(vis[b]) {
        b--;
    }
    vis[b] = 1;
    return b;
}

inline int get_min(int &a) {
    while(vis[a]) {
        a++;
    }
    vis[a] = 1;
    return a;
}

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[1] = arr[1];
    vis[arr[1]] = 1;
    int a = 1, b = 2 * n - 1;
    int p = 2;
    for(i = 2; i <= n; i++) {
        if(arr[i] == arr[i - 1]) {
            sol[p] = get_max(b);
            sol[p + 1] = get_min(a);
        }
        if(arr[i] > arr[i - 1]) {
            if(vis[arr[i]] == 0) {
                sol[p] = arr[i];
                vis[arr[i]] = 1;
                sol[p + 1] = get_max(b);
            }
            else {
                sol[p] = get_max(b);
                sol[p + 1] = get_max(b);
            }
        }
        if(arr[i] < arr[i - 1]) {
            if(vis[arr[i]] == 0) {
                sol[p] = arr[i];
                vis[arr[i]] = 1;
                sol[p + 1] = get_min(a);
            }
            else {
                sol[p] = get_min(a);
                sol[p + 1] = get_min(a);
            }
        }
        p += 2;
    }
    for(i = 1; i < 2 * n; i++) {
        cout << sol[i] << " ";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 624 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Correct 2 ms 648 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 656 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 696 KB Output is correct
2 Correct 3 ms 752 KB Output is correct
3 Correct 4 ms 996 KB Output is correct
4 Correct 6 ms 1308 KB Output is correct
5 Correct 11 ms 1916 KB Output is correct
6 Correct 20 ms 2816 KB Output is correct
7 Correct 33 ms 4344 KB Output is correct