oj.uz

Submission #251415

# Submission time Handle Problem Language Result Execution time Memory
251415 2020-07-21T07:32:05 Z zahra__d Cipele (COCI18_cipele) C++14
90 / 90
 51 ms 3708 KB 
# include<bits/stdc++.h>
# include<ext/pb_ds/assoc_container.hpp>
# include<ext/pb_ds/tree_policy.hpp>
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC optimize ("Ofast")

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef pair<int, int> pii;

# define int long long
# define S second
# define F first
# define kill(x) return(cout << x << '\n', 0LL)
# define debug(x) cerr<< #x << " = " << (x) << endl
# define ddebug(x, y) cerr<< #x << " = " << (x)  << ", " << #y << " = " << (y) << endl
# define tdebug(x, y, z) cerr<< #x << " = " << (x)  << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl
# define bin(x) cerr<< #x << " : " << bitset<7>(x) << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)
# define uop(x, y) pii(min(x, y), max(x, y))
# define MP(x, y) make_pair(x, y)

const int MAXN = 100 * 1000 + 10;
int n, m, 
    a[MAXN], b[MAXN];

bool check(int t)
{
	int j = 0;
	for (int i = 0; i < n; i ++)
	{
		while (j < m && abs(a[i] - b[j]) > t)
			j ++;
		if (j == m)
			return false;
		j ++;
	}
	return true;
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i ++)
		cin >> a[i];
	for (int i = 0; i < m; i ++)
		cin >> b[i];

	if (n > m)
	{
		swap(n, m);
		swap(a, b);
	}

	sort(a, a + n);
	sort(b, b + m);

	int l = -1, r = 2e9;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}

	cout << r << endl;



	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3456 KB Output is correct
2 Correct 46 ms 3708 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3704 KB Output is correct
2 Correct 46 ms 3704 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 512 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 3 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 51 ms 3064 KB Output is correct
2 Correct 29 ms 2944 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3328 KB Output is correct
2 Correct 25 ms 3072 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3064 KB Output is correct
2 Correct 44 ms 3456 KB Output is correct