HA18_lowerbound

coloriot

Aug 6th, 2024 (edited)

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 3.90 KB | None | 0 0

raw download clone embed print report

#include <iostream>
// Решение с более понятным циклом while с lower bound
using namespace std;
class String {
private:
char* data;
int length;
public:
String() : data(nullptr), length(0) {}
String(const char* str, int len) : length(len) {
data = new char[length];
for (int i = 0; i < length; i++) {
data[i] = str[i];
}
}
String(const String& other) : length(other.length) {
data = new char[length];
for (int i = 0; i < length; i++) {
data[i] = other.data[i];
}
}
~String() {
delete[] data;
}
String& operator=(const String& other) {
if (this == &other)
return *this;
delete[] data;
length = other.length;
data = new char[length];
for (int i = 0; i < length; i++) {
data[i] = other.data[i];
}
return *this;
}
bool startsWith(const String& prefix) const {
if (prefix.length > length)
return false;
for (int i = 0; i < prefix.length; i++) {
if (data[i] != prefix.data[i])
return false;
}
return true;
}
bool operator<(const String& other) const {
int minLength = length < other.length ? length : other.length;
for (int i = 0; i < minLength; i++) {
if (data[i] < other.data[i])
return true;
if (data[i] > other.data[i])
return false;
}
return length < other.length;
}
bool operator==(const String& other) const {
if (length != other.length)
return false;
for (int i = 0; i < length; i++) {
if (data[i] != other.data[i])
return false;
}
return true;
}
int size() const {
return length;
}
char operator[](int index) const {
return data[index];
}
friend istream& operator>>(istream& is, String& str) {
string buffer;
is >> buffer;
str = String(buffer.data(), buffer.size());
return is;
}
friend ostream& operator<<(ostream& os, const String& str) {
for (int i = 0; i < str.length; i++) {
os << str.data[i];
}
return os;
}
};
int findMidpoint(int left, int right) {
return (left + right) / 2;
}
int main() {
int N, Q;
cin >> N >> Q;
String* dictionary = new String[N];
for (int i = 0; i < N; ++i) {
cin >> dictionary[i];
}
int* results = new int[Q];
for (int i = 0; i < Q; ++i) {
String prefix;
int k;
cin >> k >> prefix;
int count = 0;
results[i] = -1;
int left = 0, right = N;
// Поиск за O(lgn) с использованием lower bound
while (left < right) {
int mid = findMidpoint(left, right);
if (dictionary[mid] < prefix) {
// Если mid меньше префикса, сдвигаем lower bound
left = mid + 1;
} else {
// Иначе сдвигаем upper bound
right = mid;
}
}
// Подсчет строк, начинающихся с префикса
for (int j = left; j < N; ++j) {
if (dictionary[j].startsWith(prefix)) {
count++;
if (count == k) { // Если найдена k-я строка
results[i] = j + 1;
break;
}
} else {
break;
}
}
}
for (int i = 0; i < Q; ++i) {
cout << results[i] << '\n';
}
delete[] dictionary;
delete[] results;
return 0;
}

Add Comment

Please, Sign In to add comment