Submission #894376

#	Time	Username	Problem	Language	Result	Execution time	Memory
894376		vjudge1	Cipele (COCI18_cipele)	C++17	90 / 90	544 ms	11604 KiB

cipele

#include <bits/stdc++.h>
using namespace std;

#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

const int N = 1e6 + 5;
const int M = 1e3 + 5;
const int inf = 1e9 + 123;
const ll infl = 1e15 + 10;
const int mod = 998244353;
const int P = 31;

int n, m, l[N], r[N];
bool swp;

bool check(int x){
    multiset <int> L, R;
    for(int i = 1; i <= n; i++)
        L.insert(l[i]);
    for(int i = 1; i <= m; i++){
        auto it = L.upper_bound(r[i] + x);
        if(it == L.begin())
            return false;
        it--;
        if(abs(*it - r[i]) > x)
            return false;
        // cout << *it << " from L and " << r[i] << " from R\n";
        L.erase(L.find(*it));
    }
    return true;
}

void solve() {
    cin >> n >> m;
    if(n < m){
        swap(n, m);
        swp = 1;
    }
    if(swp){
        for(int i = 1; i <= m; i++)
            cin >> r[i];
        for(int i = 1; i <= n; i++)
            cin >> l[i];
    }
    else{
        for(int i = 1; i <= n; i++)
            cin >> l[i];
        for(int i = 1; i <= m; i++)
            cin >> r[i];
    }
    sort(l + 1, l + n + 1);
    sort(r + 1, r + n + 1);
    reverse(r + 1, r + n + 1);
    int l = -1, r = 1e9 + 10, mid;

    while(r - l > 1){
        mid = (l + r) >> 1;
        if(check(mid))
            r = mid;
        else{
            // cout << "here\n";
            // cout << "mid = " << mid << "res = " << check(1) << nl;;
            l = mid;
        }
    }
    cout << r << nl;
}

/*
Test 1:
2 3
2 3
1 2 3

Test 2:
4 3
2 39 41 45
39 42 46

Test 3:
5 5
7 6 1 2 10
9 11 6 3 12


*/
signed main() {
    speed;
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
}

• 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