oj.uz

Submission #24858

# Submission time Handle Problem Language Result Execution time Memory
24858 2017-06-16T08:21:39 Z chpipis medians (balkan11_medians) C++11
20 / 100
 119 ms 20192 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 2e5 + 5;

#define left agqwq
#define right tqwpwep

int which[MAXN];
vi prv[MAXN], nxt[MAXN];
int left, right;
set<int> exist;

void updateLeft() {
    while (*exist.upper_bound(left) - left - 1 == (int)nxt[left].size()) {
        for (int j = 0; j < (int)nxt[left].size(); j++) {
            which[nxt[left][j]] = left + j + 1;
            exist.insert(left + j + 1);
        }
        left += (int)nxt[left].size() + 1;
    }
}

void updateRight() {
    while (right - *prev(exist.find(right)) - 1 == (int)prv[right].size()) {
        for (int j = 0; j < (int)prv[right].size(); j++) {
            which[prv[right][j]] = right - j - 1;
            exist.insert(right - j - 1);
        }
        right -= (int)prv[right].size() + 1;
    }
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    left = 0;
    right = 2 * n;
    exist.insert(0);
    exist.insert(2 * n);
    int x;
    scanf("%d", &x);
    int last = x;
    exist.insert(x);
    which[1] = x;
    updateLeft();
    updateRight();
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x);
        if (x == last) {
            nxt[left].pb(2 * i - 2);
            prv[right].pb(2 * i - 1);
        } else if (x > last) {
            if (!exist.count(x)) {
                exist.insert(x);
                which[2 * i - 1] = x;
            } else {
                prv[right].pb(2 * i - 1);
            }
            prv[right].pb(2 * i - 2);
        } else {
            if (!exist.count(x)) {
                exist.insert(x);
                which[2 * i - 1] = x;
            } else {
                nxt[left].pb(2 * i - 1);
            }
            nxt[left].pb(2 * i - 2);
        }
        updateLeft();
        updateRight();
        last = x;
    }
    for (int i = 1; i <= 2 * n - 1; i++)
        printf("%d ", which[i]);
    puts("");
    return 0;
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:86:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
medians.cpp:92:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
                    ^
medians.cpp:99:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

Subtask #1
20.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12180 KB Output is correct
2 Correct 3 ms 12180 KB Output is correct
3 Incorrect 3 ms 12180 KB Integer 0 violates the range [1, 59]
4 Incorrect 0 ms 12180 KB Integer 0 violates the range [1, 79]
5 Incorrect 3 ms 12180 KB Integer 0 violates the range [1, 99]
6 Correct 3 ms 12180 KB Output is correct
7 Incorrect 3 ms 12180 KB Integer 0 violates the range [1, 139]
8 Incorrect 0 ms 12180 KB Integer 0 violates the range [1, 159]
9 Incorrect 0 ms 12180 KB Integer 0 violates the range [1, 179]
10 Correct 3 ms 12180 KB Output is correct
11 Incorrect 0 ms 12180 KB Integer 0 violates the range [1, 599]
12 Incorrect 0 ms 12180 KB Integer 0 violates the range [1, 1199]
13 Incorrect 0 ms 12180 KB Integer 0 violates the range [1, 1999]

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12444 KB Integer 0 violates the range [1, 3999]
2 Incorrect 3 ms 12312 KB Integer 0 violates the range [1, 7999]
3 Incorrect 9 ms 12840 KB Integer 0 violates the range [1, 15999]
4 Incorrect 16 ms 13152 KB Integer 0 violates the range [1, 31999]
5 Incorrect 23 ms 13124 KB Integer 0 violates the range [1, 63999]
6 Incorrect 49 ms 15680 KB Integer 0 violates the range [1, 127999]
7 Incorrect 119 ms 20192 KB Integer 0 violates the range [1, 199999]