| Цитата(Riddik @ 3.7.2009, 12:11) | | kamre на С++ сделал за 0.312 сек |
Еще раз переписал без использования std::set, вот такой код получился: | Код | #include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <iostream>
using namespace std;
void readAssociations(map<string, vector<int> > & item_associations,
vector<string> & all_associations)
{
int items_count;
cin >> items_count;
cin.ignore();
string line;
string name;
string association;
istringstream iss;
map<string, int> association_index;
while (items_count--) {
getline(cin, name, ':');
getline(cin, line);
iss.str(line);
vector<int> & associations = item_associations[name];
while (iss >> association) {
map<string, int>::iterator iter = association_index.find(association);
if (iter != association_index.end()) {
associations.push_back(iter->second);
} else {
int index = all_associations.size();
association_index[association] = index;
associations.push_back(index);
all_associations.push_back(association);
}
}
iss.clear();
}
}
struct compare {
const vector<string> & _vect;
compare(const vector<string> & vect) : _vect(vect) {}
bool operator () (int idx0, int idx1) {
return _vect[idx0] < _vect[idx1];
}
};
void sortAssociations(map<string, vector<int> > & item_associations,
const vector<string> & all_associations,
vector<int> & to_sorted)
{
// to_sorted maps indexes to indexes in sorted vector of associations
size_t sz = all_associations.size();
to_sorted.resize(sz);
// initialize with identity
for (size_t i = 0; i < sz; ++i) {
to_sorted[i] = i;
}
// create mapping
sort(to_sorted.begin(), to_sorted.end(), compare(all_associations));
// from_sorted is inverse of mapping to_sorted
vector<int> from_sorted(sz);
for (size_t i = 0; i < sz; ++i) {
from_sorted[to_sorted[i]] = i;
}
// apply from_sorted mapping to associations indexes for all items
// and sort associations indexes
map<string, vector<int> >::iterator iter;
for (iter = item_associations.begin(); iter != item_associations.end(); ++iter) {
vector<int> & associations = iter->second;
for (size_t i = 0; i < associations.size(); ++i) {
associations[i] = from_sorted[associations[i]];
}
sort(associations.begin(), associations.end());
}
}
void processQuery(const vector<string> & query,
const map<string, vector<int> > & item_associations,
const vector<string> & all_associations,
const vector<int> & to_sorted)
{
vector<string>::const_iterator name_it = query.begin();
const vector<int> & associations = item_associations.find(*name_it)->second;
vector<int> common(associations.size());
copy(associations.begin(), associations.end(), common.begin());
while (++name_it != query.end()) {
const vector<int> & associations = item_associations.find(*name_it)->second;
vector<int>::iterator end;
end = set_intersection(common.begin(),
common.end(),
associations.begin(),
associations.end(),
common.begin());
if (end != common.end())
common.erase(end, common.end());
if (common.empty())
break;
}
if (common.empty()) {
cout << "No solution.\n";
} else {
vector<int>::const_iterator iter = common.begin();
cout << all_associations[to_sorted[*iter++]];
while (iter != common.end()) {
cout << ' ' << all_associations[to_sorted[*iter++]];
}
cout << '\n';
}
}
void processQueries(const map<string, vector<int> > & item_associations,
const vector<string> & all_associations,
const vector<int> & to_sorted)
{
int queries_count;
cin >> queries_count;
cin.ignore();
string line;
string name;
istringstream iss;
vector<string> query;
while (queries_count--) {
query.clear();
getline(cin, line);
iss.str(line);
while (iss >> name)
query.push_back(name);
iss.clear();
processQuery(query, item_associations, all_associations, to_sorted);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "rt", stdin);
#endif
map<string, vector<int> > item_associations;
vector<string> all_associations;
vector<int> to_sorted;
readAssociations(item_associations, all_associations);
sortAssociations(item_associations, all_associations, to_sorted);
processQueries(item_associations, all_associations, to_sorted);
return 0;
} |
|
Самый быстрый способ сортировки строк 
Загрузка ...
