oj.uz

Submission #165476

# Submission time Handle Problem Language Result Execution time Memory
165476 2019-11-27T11:13:06 Z Sensei Cipele (COCI18_cipele) C++17
90 / 90
 109 ms 4056 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

bool check (deque<int> a, deque<int> b, int val) {
	if (a.size() > b.size()) {
		swap(a, b);
	}

	for (int i = 0; i < a.size(); i++) {
		while (b.size() > 0 && abs(b[0] - a[i]) > val) {
			b.pop_front();
		}

		if (b.size() == 0) {
			return false;
		}
		else {
			b.pop_front();
		}
	}

	return true;
}

int main () {
	int N, M;
	cin >> N >> M;

	deque<int> a(N);
	deque<int> b(M);

	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}

	sort(a.begin(), a.end());

	for (int i = 0; i < M; i++) {
		scanf("%d", &b[i]);
	}

	sort(b.begin(), b.end());

	int ss = 0, se = 1e9;

	int jump = 1;


	while (ss + jump * 2 <= se) {
		jump *= 2;
	}

	for (; jump > 0; jump /= 2) {
		int mid = se - jump;

		if (mid < ss) {
			continue;
		}

		if (check(a, b, mid)) {
			se = mid;
		}
		else {
			ss = mid + 1;
		}
	}

	cout << se << "\n";

	return 0;
}

Compilation message

cipele.cpp: In function 'bool check(std::deque<int>, std::deque<int>, int)':
cipele.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                  ~~^~~~~~~~~~
cipele.cpp: In function 'int main()':
cipele.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
cipele.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3560 KB Output is correct
2 Correct 101 ms 3784 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3784 KB Output is correct
2 Correct 109 ms 4056 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3108 KB Output is correct
2 Correct 61 ms 2324 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3568 KB Output is correct
2 Correct 49 ms 2728 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 3144 KB Output is correct
2 Correct 88 ms 3356 KB Output is correct