Всем привет. Сделал маленькую прогу по добавлению и проверке синонимов для курса Яндекса. Как раз контейнер set прохожу. Задание тут Ссылка на задание курса если вдруг важно.
#include <iostream>
#include <string>
#include <set>
using namespace std;
void Count_sin(const set<set<string>>& sinon, const string& word) {
int key = 0;
for (const auto& z : sinon) { //роемся в "большом" множестве
for (const auto& y : z) { //и в каждом слове "маленького" множества
if (y == word) { //ищем совпадение со словом, и если нашли
key++; //плюсанули себе за то что нашли
}
}
}
cout << key << endl; //выводим сколько раз плюсанули себе
}
void Check_sin(const set<set<string>>& sinon, const string& word1, const string& word2) {
set<string> sett = { word1, word2 }; //создаем из слов "маленькое" множество
int key = 0; //объявили ключ для проверки наличия синонима
for (const auto& z : sinon) { //в каждом множестве "большого" множества
if (z == sett) { //ищем совпадение
cout << "YES" << endl; //и если нашли, то пишем ДА
key++; //плюсанули себе
}
}
if (key == 0) { //если не плюсанули себе, то
cout << "NO" << endl; //пишем НЕТ
}
}
int main() {
int i;
string comand, word1, word2;
set<set<string>> sinon; //создадим "большое" множество "маленьких" множеств
cin >> i; //количество строк запросов
for (i; i > 0; i--) {
cin >> comand; //считываем команду
if (comand == "ADD") { //проверяем какая команда пришла
cin >> word1 >> word2; //считываем слова
sinon.insert({ word1, word2 }); //вставляем слова в "большое" множество
}
else if (comand == "COUNT") {
string word;
cin >> word; //считываем слово
Count_sin(sinon, word); //узнаем сколько синонимов у слова
}
else if (comand == "CHECK") {
string word1, word2;
cin >> word1 >> word2; //считали слова
Check_sin(sinon, word1, word2); //проверяем, есть ли такая пара
}
}
return 0;
}
На одном из его тестов прога выполняется дольше 1 секунды. (Failed case #8/16: time limit exceeded (Time used: 1.99/1.00)) Нужно не более 1 секунды. На простых тестах отрабатывает быстро (менее 0,04 сек). Где может быть потеря времени, и почему?
Новый код:
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
int i, key;
string comand, word1, word2, word;
set<set<string>> sinon;
cin >> i;
for (i; i > 0; i--) {
cin >> comand;
if (comand == "ADD") {
cin >> word1 >> word2;
sinon.insert({ word1, word2 });
}
else if (comand == "COUNT") {
cin >> word;
key = 0;
for (auto& z : sinon) { //ссылка есть
key += z.count(word); //и функция
}
cout << key << endl;
}
else if (comand == "CHECK") {
cin >> word1 >> word2;
if (sinon.count({word1, word2})){ //и тут функция
cout << "YES" << endl;
}
else cout << "NO" << endl;
}
}
return 0;
}
Все равно долго считает. Уже не знаю что делать.
Само задание...
Два слова называются синонимами друг друга, если они имеют похожие значения. Реализуйте следующие операции над словарём синонимов: ADD word1 word2 — добавить в словарь пару синонимов (word1, word2). COUNT word — узнать количество синонимов слова word. CHECK word1 word2 — проверить, являются ли слова word1 и word2 синонимами. Слова word1 и word2 считаются синонимами, если среди запросов ADD был хотя бы один запрос ADD word1 word2 или ADD word2 word1.
Формат ввода
Сначала вводится количество запросов Q, затем Q строк с описаниями запросов. Гарантируется, что в каждом запросе CHECK и ADD слова word1 и word2 различны. Все слова состоят лишь из латинских букв, цифр и символов подчёркивания.
Формат вывода
Для каждого запроса в соответствующей строке выведите ответ на него: В ответ на запрос COUNT word выведите единственное целое число — количество синонимов слова word. В ответ на запрос CHECK word1 word2 выведите строку YES, если word1 и word2 являются синонимами, и NO в противном случае.
Итоговое решение
#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;
using sorted_pair = pair<string, string>;
sorted_pair make_sorted_pair(const std::string& word1, const string& word2) {
return (word1 <= word2) ? make_pair(word1, word2) : make_pair(word2, word1);
}
bool check(const set<sorted_pair>& synonyms, const string& word1, const string& word2) {
return synonyms.count(make_sorted_pair(word1, word2)) != 0;
}
void add(set<sorted_pair>& synonyms, map<string, unsigned>& synonyms_count, const string& word1, const string& word2) {
if (check(synonyms, word1, word2)) return; // синоним уже есть
++synonyms_count[word1];
++synonyms_count[word2];
synonyms.insert(make_sorted_pair(word1, word2));
}
int main() {
set<sorted_pair> synonyms; // пары синонимов
map<string, unsigned> synonyms_count; // количество синонимов
int i;
string comand, word1, word2;
cin >> i; //количество запросов
for (i; i > 0; i--) {
cin >> comand; //считываем комманду
if (comand == "ADD") { //проверяем какая комманда пришла
cin >> word1 >> word2; //считываем слова
add(synonyms, synonyms_count, word1, word2);
}
else if (comand == "COUNT") {
string word;
cin >> word; //считываем слово
cout << synonyms_count[word] << endl;
}
else if (comand == "CHECK") {
string word1, word2;
cin >> word1 >> word2; //прочитали слова
if (check(synonyms, word1, word2)){
cout << "YES" << endl; //пишем Да
}
else cout << "NO" << endl; //иначе НЕТ
}
}
return 0;
}
multimap
? Как по мне, прямо просится сюда...