제출 #170615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170615		BigChungus	Cipele (COCI18_cipele)	C++14	90 / 90	50 ms	3064 KiB

cipele

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9