oj.uz

Submission #894376

# Submission time Handle Problem Language Result Execution time Memory
894376 2023-12-28T07:32:17 Z vjudge1 Cipele (COCI18_cipele) C++17
90 / 90
 544 ms 11604 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 11464 KB Output is correct
2 Correct 489 ms 11604 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 11464 KB Output is correct
2 Correct 486 ms 11604 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2652 KB Output is correct
2 Correct 15 ms 2552 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2652 KB Output is correct
2 Correct 15 ms 2652 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2652 KB Output is correct
2 Correct 16 ms 2784 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 15 ms 2788 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 15 ms 2796 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 11180 KB Output is correct
2 Correct 247 ms 7512 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 11132 KB Output is correct
2 Correct 366 ms 11088 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 10864 KB Output is correct
2 Correct 408 ms 10692 KB Output is correct