oj.uz

Submission #170615

# Submission time Handle Problem Language Result Execution time Memory
170615 2019-12-25T19:32:34 Z BigChungus Cipele (COCI18_cipele) C++14
90 / 90
 50 ms 3064 KB 
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 1e5 + 7;

int l[N], r[N], aux[N];

int n, m;

bool possible(int val) {
    int curj(1);
    for (int i = 1; i <= n; ++i) {
        while (curj <= m && r[curj] + val < l[i])
            ++curj;
        if (curj > m)
            return 0;
        if (r[curj] > l[i] + val)
            return 0;
        ///acum practic am imperecheat i cu curj
        ++curj;
    }
    return 1;
}

int bs() {
    int pas(1<<29), r(-1);
    while (pas) {
        if (!possible(r + pas))
            r += pas;
        pas >>= 1;
    }
    return r + 1;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> l[i];
    for (int i = 1; i <= m; ++i)
        cin >> r[i];
    if (n > m) {
        for (int i = 1; i <= n; ++i)
            aux[i] = l[i];
        swap(n, m);
        for (int i = 1; i <= n; ++i)
            l[i] = r[i];
        for (int j = 1; j <= m; ++j)
            r[j] = aux[j];
    }
    sort(l + 1, l + n + 1);
    sort(r + 1, r + m + 1);
    cout << bs();
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2680 KB Output is correct
2 Correct 50 ms 3064 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2940 KB Output is correct
2 Correct 50 ms 2960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2480 KB Output is correct
2 Correct 31 ms 2012 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2584 KB Output is correct
2 Correct 25 ms 2592 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2424 KB Output is correct
2 Correct 44 ms 2908 KB Output is correct