oj.uz

Submission #49959

# Submission time Handle Problem Language Result Execution time Memory
49959 2018-06-05T10:52:11 Z mra2322001 medians (balkan11_medians) C++14
95 / 100
 119 ms 13244 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 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 664 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 3 ms 680 KB Output is correct
12 Incorrect 2 ms 808 KB Not a permutation
13 Correct 3 ms 872 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 5 ms 1292 KB Output is correct
3 Correct 8 ms 1692 KB Output is correct
4 Correct 15 ms 2604 KB Output is correct
5 Correct 32 ms 4668 KB Output is correct
6 Correct 71 ms 8832 KB Output is correct
7 Correct 119 ms 13244 KB Output is correct