oj.uz

Submission #49958

# Submission time Handle Problem Language Result Execution time Memory
49958 2018-06-05T10:51:23 Z mra2322001 medians (balkan11_medians) C++14
0 / 100
 129 ms 15264 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 < 2*n; i++){
        if(i != a[1]) 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 = 2; i <= n; 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:21: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:21: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
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Not a permutation
2 Runtime error 7 ms 872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 2 ms 872 KB Not a permutation
4 Incorrect 2 ms 872 KB Not a permutation
5 Runtime error 5 ms 872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 2 ms 872 KB Not a permutation
7 Incorrect 2 ms 872 KB Not a permutation
8 Incorrect 2 ms 872 KB Not a permutation
9 Runtime error 4 ms 988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 2 ms 988 KB Not a permutation
11 Runtime error 5 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 2 ms 1100 KB Not a permutation
13 Incorrect 2 ms 1100 KB Not a permutation

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1348 KB Not a permutation
2 Incorrect 5 ms 1488 KB Not a permutation
3 Runtime error 10 ms 2828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 17 ms 4644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 32 ms 6816 KB Not a permutation
6 Incorrect 75 ms 10884 KB Not a permutation
7 Incorrect 129 ms 15264 KB Not a permutation