oj.uz

Submission #222626

# Submission time Handle Problem Language Result Execution time Memory
222626 2020-04-13T13:00:20 Z Bruteforceman medians (balkan11_medians) C++11
100 / 100
 123 ms 12152 KB 
#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

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.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 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 6 ms 384 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 672 KB Output is correct
2 Correct 8 ms 768 KB Output is correct
3 Correct 13 ms 1280 KB Output is correct
4 Correct 22 ms 2176 KB Output is correct
5 Correct 38 ms 4088 KB Output is correct
6 Correct 75 ms 7800 KB Output is correct
7 Correct 123 ms 12152 KB Output is correct