oj.uz

Submission #314415

# Submission time Handle Problem Language Result Execution time Memory
314415 2020-10-19T20:17:27 Z mohamedsobhi777 Cipele (COCI18_cipele) C++14
90 / 90
 48 ms 3324 KB 
#include <bits/stdc++.h>

/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 7, mod = 1e9 + 7;
const int inf = N;
// How interesting!

int n, m;
vector<int> v1, v2;

bool check(int x)
{
        int j = 0;
        for (int i = 0; i < n; ++i, ++j)
        {
                while (j < m && abs(v2[j] - v1[i]) > x)
                        ++j;
                if (j >= m)
                        return 0;
        }
        return 1;
}

int main()
{

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
        {
                int x;
                cin >> x;
                v1.push_back(x);
        }
        for (int i = 0; i < m; ++i)
        {
                int x;
                cin >> x;
                v2.push_back(x);
        }
        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end());
        if (n > m)
        {
                swap(n, m);
                swap(v1, v2);
        }
        int lo = 0, hi = 1e9;
        int ans = 0;
        while (lo <= hi)
        {
                int mid = (lo + hi) >> 1;
                if (check(mid))
                {
                        hi = mid - 1;
                        ans = mid;
                }
                else
                        lo = mid + 1;
        }
        cout << ans;
        return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3068 KB Output is correct
2 Correct 45 ms 3196 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3324 KB Output is correct
2 Correct 46 ms 3188 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 508 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2940 KB Output is correct
2 Correct 27 ms 1920 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2940 KB Output is correct
2 Correct 23 ms 2300 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2812 KB Output is correct
2 Correct 39 ms 2936 KB Output is correct