oj.uz

Submission #49957

# Submission time Handle Problem Language Result Execution time Memory
49957 2018-06-05T10:42:27 Z mra2322001 medians (balkan11_medians) C++14
95 / 100
 159 ms 14580 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100002;
const int R = 2*N;

int n, a[N], b[R], dd[R], save[N];
int d[2*N];
set <int> s;

void up(){
    for(int i = 1; i < n; i++){
        d[a[i]] = 1;
    }
    for(int i = 1; i <= 2*n - 1; i++){
        if(d[i]==0) s.insert(i);
    }
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1];
    for(int i = 2; i <= n; i++){
        if(dd[a[i]]==0) dd[a[i]] = i;
        if(a[i] > a[i - 1]){
            /// 1 nho hon, 3 lon hon, 2 nguoc lai
            save[i] = 3;
        }
        else if(a[i] < a[i - 1]) save[i] = 1;
        else save[i] = 2;
    }
    up();
    for(int i = n; i > 1; i--){
        /// 2*i - 1, 2*i - 2
        if(save[i]==1){
            if(dd[a[i]]==i){
                b[2*i-1] = a[i];
                auto it = s.lower_bound(a[i]); --it;
                b[2*i-2] = *it;
                s.erase(a[i]); s.erase(*it);
            }
            else{
                auto it = s.lower_bound(a[i]); --it;
                b[2*i-1] = *it; s.erase(*it);
                it = s.lower_bound(a[i]); --it;
                b[2*i-2] = *it; s.erase(*it);
            }
        }
        else if(save[i]==2){
            auto it = s.lower_bound(a[i]); --it;
            b[2*i-1] = *it; s.erase(*it);
            it = s.upper_bound(a[i]);
            b[2*i-2] = *it; s.erase(*it);
        }
        else{
            if(dd[a[i]]==i){
                b[2*i-1] = a[i]; s.erase(a[i]);
                auto it = s.lower_bound(a[i]);
                b[2*i-2] = *it; s.erase(*it);
            }
            else{
                auto it = s.upper_bound(a[i]);
                b[2*i-1] = *it; s.erase(*it);
                it = s.upper_bound(a[i]);
                b[2*i-2] = *it; s.erase(it);
            }
        }
    }
    for(int i = 1; i < 2*n; i++) cout << b[i] << " ";
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:24:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1];
     ^~~
medians.cpp:24:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1];
                                              ^

Subtask #1
60.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Incorrect 2 ms 848 KB Not a permutation
13 Correct 3 ms 908 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1056 KB Output is correct
2 Correct 4 ms 1276 KB Output is correct
3 Correct 8 ms 1888 KB Output is correct
4 Correct 14 ms 2952 KB Output is correct
5 Correct 34 ms 5308 KB Output is correct
6 Correct 68 ms 9652 KB Output is correct
7 Correct 159 ms 14580 KB Output is correct