oj.uz

Submission #627435

# Submission time Handle Problem Language Result Execution time Memory
627435 2022-08-12T15:05:37 Z Farhan_HY Cipele (COCI18_cipele) C++14
90 / 90
 840 ms 8468 KB 
#include <bits/stdc++.h>
#define int long long
#define float double
#define pb push_back
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
/// Benzema is the best player in the world
const int inf = 8e18;
const int N = 1e5 + 5;
const int M = 1e3 + 3;
const int LOG = 31;
const int mod = 1e9 + 7;
const float pi = atan(1) * 4;
int a[N], b[N], n, m;
multiset<int> st;

bool ok(int mid)
{
    st.clear();
    for(int i = 1; i <= m; i++)
        st.insert(b[i]);
    bool ret = 1;
    for(int i = 1; i <= n; i++)
    {
        int need = a[i] - mid;
        auto it = st.lower_bound(need);
        ret &= it != st.end();
        if (it != st.end())
        {
            ret &= abs(a[i] - *it) <= mid;
            st.erase(it);
        }
    }
    return ret;
}

main()
{
    IOS
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int j = 1; j <= m; j++)
        cin >> b[j];
    if (n > m)
        swap(n, m), swap(a, b);
    sort(a, a + n + 1);
    int l = 0, r = 1e9;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if (ok(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r;
}
///use scanf

Compilation message

cipele.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main()
      | ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 8116 KB Output is correct
2 Correct 761 ms 8468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 8376 KB Output is correct
2 Correct 799 ms 8368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Output is correct
2 Correct 21 ms 752 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 640 KB Output is correct
2 Correct 20 ms 724 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 596 KB Output is correct
2 Correct 21 ms 728 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 596 KB Output is correct
2 Correct 21 ms 724 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 572 KB Output is correct
2 Correct 26 ms 724 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 7584 KB Output is correct
2 Correct 444 ms 5692 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 7680 KB Output is correct
2 Correct 477 ms 7104 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 7256 KB Output is correct
2 Correct 745 ms 7408 KB Output is correct