oj.uz

Submission #894370

# Submission time Handle Problem Language Result Execution time Memory
894370 2023-12-28T07:27:00 Z vjudge1 Cipele (COCI18_cipele) C++17
0 / 90
 76 ms 11356 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 = 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 11348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Incorrect 3 ms 2788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 11320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 11144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 10836 KB Output isn't correct
2 Halted 0 ms 0 KB -