RB2.12 Практические применения

RobertDeMilo

Apr 16th, 2024

Never

Add comment

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

C++ 2.56 KB | None | 0 0

raw download clone embed print report

#include<iostream>
#include<string>
#include<map>
#include<set>
using namespace std;
int main()
{
int q;
cin >> q;
map<string, set<string>> synonyms;
for (int i = 0; i < q; i++) // Q итераций
{
string operation_code;
cin >> operation_code;
if (operation_code == "ADD")
{
string first_word, second_word;
cin >> first_word >> second_word; // L
synonyms[first_word].insert(second_word); // LlogQ
synonyms[second_word].insert(first_word);
// O(LlogQ)
}
else if (operation_code == "COUNT")
{
string word;
cin >> word;
cout << synonyms[word].size()<<endl;
// O(LlogQ)
}
else if (operation_code == "CHECK")
{
string first_word, second_word;
cin >> first_word >> second_word;
if (synonyms[first_word].count(second_word)==1)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
// O(LlogQ)
}
// O(QLlogQ)
}
return 0;
}
////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <map>
using namespace std;
static string FindNameByYear(const map<int,string>&names, int year)
{
string name;
for(const auto& item:names) //O(Q)
{
if(item.first<=year) //O(1)
{
name=item.second; //O(L)
}
else
{
break;
}
}
return name;
// O(QL)
}
static string FindNameByYear2(const map<int, string>&names, int year)
{
auto iter_after = names.upper_bound(year);
string name;
if(iter_after!=names.begin())
{
name =(--iter_after)->second;
}
return name;
// O(LogQ + L)
}
class Person
{
public:
void ChangeFirstName(int year, const string& first_name)
{
first_names[year]= first_name;
// Q(LogQ+L)
}
void ChangeLastName(int year, const string& last_name)
{
last_names[year]= last_name;
// Q(LogQ+L)
}
string GetFullName(int year)
{
const string first_name = FindNameByYear(first_names,year);
const string last_name = FindNameByYear(last_names,year);
if(first_name.empty()&&last_name.empty())
{
return "Incognito";
}
else if(first_name.empty())
{
return last_name+ " with unknown first name";
}
else if(last_name.empty())
{
return first_name+ " with unknown last name";
}
else
{
return first_name + " " + last_name;
}
// O(L) + O(QL) = O(QL)
// O(LogQ + L)
}
private:
map<int,string>first_names;
map<int,string>last_names;
};
// O(Q^2 * L)
// O(Q * (L + LogQ))
int main()
{
return 0;
}

Add Comment

Please, Sign In to add comment