В первой строке даны целое число 1≤n≤10^5 и массив A[1…n] из n различных натуральных чисел, не превышающих 10^9, в порядке возрастания, во второй — целое число 1≤k≤10^5 и k натуральных чисел b1,…,bk, не превышающих 10^9. Для каждого i от 1 до k необходимо вывести индекс 1≤j≤n, для которого A[j]=bi, или −1, если такого j нет.
Sample Input:
5 1 5 8 12 13
5 8 1 23 1 11
Sample Output: 3 1 -1 1 -1
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
int get_pos(const vector<int> &numbers, int number) {
vector<int> ::const_iterator it = find(numbers.begin(), numbers.end(), number);
if (it == numbers.end()) {
return -1;
}
return static_cast<int>(it - numbers.begin()) + 1;
}
int main(void) {
size_t number_count;
cin >> number_count;
vector<int> numbers(number_count);
for (size_t i = 0; i < number_count; i++) {
cin >> numbers[i];
}
size_t query_count;
cin >> query_count;
while (query_count-- > 0) {
int number;
cin >> number;
cout << get_pos(numbers, number) << " ";
}
cout << endl;
} |
|
Failed test #3. Time limit exceeded
Как функцию поправить, чтобы ускорить?
Добавлено через 17 минут
| C++ |
1
2
3
4
5
6
7
| int mid = ( low + high ) / 2;
if ( A[mid] == key )
return mid;
if ( A[mid] < key)
BinSearch(A,key,mid+1,high);
if ( A[mid] > key )
BinSearch(A,key,low,mid-1); |
|
как это в код вставить, чтоб все работало путево?
Добавлено через 7 часов 8 минут
А вот так
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
int get_pos(const std::vector<int> &numbers, int number) {
// TODO optimize this function
size_t l = 0;
size_t r = numbers.size();
while (l + 1 < r) {
size_t m = l + (r-l) / 2;
if (numbers[m] > number) {
r = m;
} else {
l = m;
}
}
if (l == r || numbers[l] != number) {
return -1;
}
return l + 1;
}
int main(void) {
std::vector<int> numbers;
size_t number_count;
std::cin >> number_count;
numbers.resize(number_count);
for (auto &number:numbers) {
std::cin >> number;
}
assert(std::is_sorted(numbers.begin(), numbers.end()));
size_t query_count;
std::cin >> query_count;
while (query_count-- > 0) {
int number;
std::cin >> number;
std::cout << get_pos(numbers, number) << " ";
}
std::cout << std::endl;
} |
|
Спасибо. Тема закрыта.
(
