shayan.eftekhari
BAN USERbool preorder(vector<unordered_multiset<string>> starts_with, vector<unordered_multiset<string>> ends_with, list<string>& answer, size_t goal_size)
{
const auto& first_name = answer.front();
const auto& last_name = answer.back();
auto start_char = first_name[0];
auto end_char = last_name[last_name.size() - 1];
if (!starts_with[end_char - 'a'].empty())
{
for (auto next_name : starts_with[end_char - 'a'])
{
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
answer.push_back(next_name);
if (answer.size() == goal_size)
return true;
starts_with_copy[next_name[0] - 'a'].erase(next_name);
ends_with_copy[next_name[next_name.size() - 1] - 'a'].erase(next_name);
if (preorder(starts_with_copy, ends_with_copy, answer, goal_size))
return true;
answer.pop_back();
}
}
else
{
if (!ends_with[start_char - 'a'].empty())
for (auto next_name : ends_with[start_char - 'a'])
{
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
answer.push_front(next_name);
if (answer.size() == goal_size)
return true;
starts_with_copy[next_name[0] - 'a'].erase(next_name);
ends_with_copy[next_name[next_name.size() - 1] - 'a'].erase(next_name);
if (preorder(starts_with_copy, ends_with_copy, answer, goal_size))
return true;
answer.pop_front();
}
else
return false;
}
return false;
}
void sort_names()
{
size_t count; cin >> count;
vector<string> names(count); for (size_t i = 0; i < count; ++i) cin >> names[i];
names.erase(
remove_if(begin(names), end(names), [](const string& name) { return name.empty(); }),
cend(names)
);
for_each(begin(names), end(names), [](string& name) { transform(cbegin(name), cend(name), begin(name), tolower); });
vector<unordered_multiset<string>> starts_with(26);
vector<unordered_multiset<string>> ends_with(26);
for (const auto& name : names)
{
auto start_char = name[0];
auto end_char = name[name.size() - 1];
starts_with[start_char - 'a'].insert(name);
ends_with[end_char - 'a'].insert(name);
}
for (const auto& name : names)
{
list<string> answer{ name };
auto starts_with_copy = starts_with;
auto ends_with_copy = ends_with;
starts_with_copy[name[0] - 'a'].erase(name);
ends_with_copy[name[name.size() - 1] - 'a'].erase(name);
if (preorder(starts_with_copy, ends_with_copy, answer, names.size()))
{
for (const auto& item : answer)
cout << item << ' ';
cout << endl;
}
}
}
int main()
{
string line;
getline(cin, line);
istringstream ss(line);
unordered_set<string> keywords;
string word;
while (ss >> word)
{
transform(cbegin(word), cend(word), begin(word), tolower);
keywords.emplace(word);
}
unordered_map<int, int> hotel_keywords_count;
int review_count;
cin >> review_count;
int hotel_id;
for (int i = 0; i < review_count; ++i)
{
cin >> hotel_id;
int& keywords_count = hotel_keywords_count[hotel_id];
cin.ignore();
getline(cin, line);
ss.clear();
ss.str(line);
while (ss >> word)
{
transform(cbegin(word), cend(word), begin(word), tolower);
regex e("[^[:alpha:]]");
word = regex_replace(word, e, "");
if (keywords.find(word) != cend(keywords))
++keywords_count;
}
}
list<pair<int, int>> hotels_list;
copy(cbegin(hotel_keywords_count), cend(hotel_keywords_count), back_inserter(hotels_list));
hotels_list.sort([](const pair<int, int>& p1, const pair<int, int>& p2){
if (p1.second == p2.second)
return p1.first < p2.first;
return p1.second > p2.second;
});
for (auto& item : hotels_list)
cout << item.first << " ";
cout << endl;
}
enum square_state
{
BLACK,
WHITE,
EMPTY,
OUT_OF_BOUND
};
// Suppose board and visited are filled.
vector<vector<square_state>> board;
vector<vector<bool>> visited;
square_state getState(int x, int y)
{
if (x < 0 || x > 3 || y < 0 || y > 3)
return OUT_OF_BOUND;
return board[x][y];
}
bool is_captured(int x, int y)
{
queue<pair<int, int>> q;
q.emplace(x, y);
while (!q.empty())
{
auto cur_cell = q.front();
auto cur_cell_state = getState(cur_cell.first, cur_cell.second);
q.pop();
if (cur_cell_state == EMPTY || cur_cell_state == OUT_OF_BOUND)
return false;
auto up_cell = make_pair(cur_cell.first, cur_cell.second - 1);
auto up_cell_state = getState(up_cell.first, up_cell.second);
if (up_cell_state == EMPTY)
return false;
if (!visited[up_cell.first][up_cell.second] && cur_cell_state == up_cell_state)
q.emplace(up_cell);
auto down_cell = make_pair(cur_cell.first, cur_cell.second + 1);
auto down_cell_state = getState(down_cell.first, down_cell.second);
if (down_cell_state == EMPTY)
return false;
if (!visited[down_cell.first][down_cell.second] && cur_cell_state == down_cell_state)
q.emplace(down_cell);
auto left_cell = make_pair(cur_cell.first - 1, cur_cell.second);
auto left_cell_state = getState(left_cell.first, left_cell.second);
if (left_cell_state == EMPTY)
return false;
if (!visited[left_cell.first][left_cell.second] && cur_cell_state == left_cell_state)
q.emplace(left_cell);
auto right_cell = make_pair(cur_cell.first + 1, cur_cell.second);
auto right_cell_state = getState(right_cell.first, right_cell.second);
if (right_cell_state == EMPTY)
return false;
if (!visited[right_cell.first][right_cell.second] && cur_cell_state == right_cell_state)
q.emplace(right_cell);
visited[cur_cell.first][cur_cell.second] = true;
}
return true;
}
Repdavisjerryh, Backend Developer at Abs india pvt. ltd.
For the last two years, I am Effectively managing the team’s performance, conducting regular performance reviews and appraisals, and ...
- shayan.eftekhari April 09, 2019