Превышение лимита памяти на простой задачке.
Ограничение времени 3 секунды
Ограничение памяти 64Mb
В языке Страны Чудес заимствования иностранных терминов происходят следующим способом: если термин начинается с “w”, то он переходит в язык Страны Чудес без изменений, если начинается с другой буквы — к нему спереди дописывается буква “w” (первая буква названия страны — Wonderland). Так, “linux” на языке Страны Чудес — “wlinux”, а “windows” — “windows”.
Попав в Страну Чудес, Алиса купила словарь терминов, содержавший N/2 пар “исходный термин — местный термин” Причём все исходные термины в словаре не совпадали с местными, то есть не начинались буквой “w”. Однако по пути словарь упал на пол, слова в нём перемешались, и одно слово — неизвестно, исходный термин или термин на языке Страны Чудес — выпало и потерялось.
Вам даны слова в том порядке, в котором они сохранились в словаре. Гарантируется, что для каждого слова, кроме одного, присутствует и само слово, и его перевод на язык Страны Чудес, а для оставшегося слова присутствует либо исходный термин, либо его перевод. Требуется найти пропавшее слово.
Формат ввода
Первая строка входных данных содержит одно целое нечётное число N — количество оставшихся в словаре слов (1 ≤ N ≤ 10^7).
Каждая из последующих N строк содержит одно непустое слово длины, не превосходящей 1000, состоящее из строчных латинских букв — одно из оставшихся в словаре слов.
Гарантируется, что словарь мог быть получен описанным в задаче образом и что общее количество символов в словаре не превосходит 10^8.
Формат вывода
Выведите потерявшееся слово.
Мой код:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
unordered_map<string, int> m;
string s;
for(int i = 0; i <n; i++){
cin >> s;
m[s] = 1;
}
for(auto &[WORD, COUNT] : m){
if(WORD[0] == 'w'){
string ewn = WORD.substr(1, WORD.size()-1);
if(m.find(ewn) == m.end()){
cout << ewn;
return 0;
}
}else{
string ewn = "w"+WORD;
if(m.find(ewn) == m.end()){
cout << ewn;
return 0;
}
}
}
return 0;
} Последние 6 тестов ложатся с MLE. unordered_set<string> пытался делать, но словил MLE на 15 и WA на 2.
Можете, пожалуйста, помочь с оптимизацией?
#include <iostream>
#include <set>
using namespace std;
int main()
{
set <string> words; //храним тут слова без первого w
size_t n;
long long cnt = 0; //для определения w или не w потерянное слово
cin >> n;
while (n--)
{
cin.ignore(); //удаляем символ перехода на новую строку
string str;
if (cin.peek() == 'w') { cin.ignore(); cnt++; }
//проверяем первую букву перед записью, если это w - игнорим ее
else cnt--;
//и считаем баланс букв w
cin >> str; //считываем слово
if (words.contains(str)) words.erase(str); else words.insert(str);
//если такое есть - удаляем, если нет - добавляем в сет.
}
if (cnt == -1) cout << 'w'; //восстанавливаем букву w при необходимости
cout << *words.begin(); //выводим оставшееся слово в сете
} 10 миллионов слов по 1 тыс символов, даже с общим ограничением в 100 миллионов символов, плюс накладные расходы RTL и контейнеров - это далеко не 64 мегабайта.
По убыванию влияния на память:
Во-первых, судя по условию, это - словарь без синонимов и только с одним частично присутствующим словом. Поэтому при обнаружении во входных данных одной из версий слова добавляем слово в словарь, а при обнаружении второй версии - удаляем первую из словаря. После обработки всего потока в словаре останется одно слово.
Во-вторых, совершенно не нужно хранить и само слово, и его w-версию. Это - дублирование данных и порождение кучи лишних и запутанных условий в ходе. Храни ключом только слово без w, а в значении отражай, какая из его версий присутствует. Хотя, тут и значение неважно, т.к. если мы встретили слово wlinux (и добавили в словарь ключом linux), то дальше может встретиться только linux или вообще ничего не встретится. Так что map тут не нужен, достаточно set.
В-третьих, в условиях ограниченной памяти об unordered_map/unordered_set вообще забудь, как о страшном сне. Никогда не используй эти коллекции в таких условиях.
Сделай префиксное дерево и храни словарь в нём.
Надеюсь, ты умеешь самостоятельно реализовывать структуры данных, а не только подключать готовые реализации, как научили.
Этим есть смысл заняться, если памяти всё ещё не хватает. Например, при таком расположении слов во входном потоке, что сначала идут все без w, а потом - с w, тогда в контейнер придётся сложить половину входного потока.
Например, один из граничных сценариев: 10 млн строк по 9-11 символов, в среднем 10. Если в твоей версии STL присутствует SSO (small string optimization), то это будет не менее 160 мегабайт на сами строки (по 16 байт на каждую), из которых ты будешь хранить чуть меньше половины, т.е. 5 млн строк, т.е. 80 мегабайт. Плюс накладные расходы на "вёдра" хэш-таблицы, это ещё как минимум по 8 байт, а в сумме - 40 мегабайт. И эти 120 мегабайт - на один только контейнер. Одна только замена на хэш-таблицу с открытой адресацией снизит расход памяти в полтора раза, а префиксное дерево при грамотной реализации займёт памяти ещё меньше.
В-четвёртых, избегай копирования строк. Ну вот что это такое?
string ewn = WORD.substr(1, WORD.size()-1); или вот это:
string ewn = "w"+WORD; Ты понимаешь, что происходит с т.з. памяти при выполнении таких операций? Если нет, то разберись.
Если у тебя есть строка с 'w', а ты хочешь удалить из неё первый символ, то сделай erase. Естественно, делать это можно только на строках, которыми монопольно владеет данный блок кода (на тех, которые уже лежат в словаре, - нельзя).
А для данного применения я бы вообще реализовал свою строку, оптимизированную под хранение w / без w и преобразование между ними без копирования данных и без выделения дополнительной памяти.
В-пятых, можно реализовать свой аллокатор, оптимизированный под строки. Но в данной задаче до этого вряд ли дойдёт.