http://acm.pku.edu.cn/JudgeOnline/problem?id=1109
Код:
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
int page;
int ch;
int token;
bool lookahead = false;
const int END_OF_DOCUMENT = -1;
const int END_OF_FILE = -2;
struct Entry
{
string primary;
string secondary;
int page;
Entry (string p, string s)
: primary(p), secondary(s), page(::page) {};
};
vector<Entry> entry;
int string_compare (const string& s, const string& t)
{
int m = s.length ();
int n = t.length ();
int k = m <= n ? m : n;
for (int i = 0; i < k; ++i)
{
int a = toupper (s[i]);
int b = toupper (t[i]);
if (a != b) return a - b;
}
return m == n ? 0 : m < n ? -1 : 1;
}
bool less_than (const Entry& a, const Entry& b)
{
int cmp = string_compare (a.primary, b.primary);
if (cmp < 0) return true;
if (cmp > 0) return false;
cmp = string_compare (a.secondary, b.secondary);
if (cmp < 0) return true;
if (cmp > 0) return false;
return a.page < b.page;
}
inline int next_char ()
{
if (lookahead) lookahead = false; else ch = cin.get ();
return ch;
}
int next_token ()
{
switch (next_char ())
{
case '*':
token = (next_char () == '*') ? END_OF_FILE : END_OF_DOCUMENT;
break;
case ' ': case '\n':
next_char ();
if (ch == '%' || ch == '$' || ch == '}')
token = ch;
else {
token = ' ';
lookahead = true;
break;
}
case '{': case '%': case '$':
token = ch;
lookahead = ! isspace (next_char ());
break;
default:
token = ch;
}
return token;
}
inline bool is_delimiter (int t)
{
return t == '%' || t == '$' || t == '}';
}
void add_entry ()
{
string primary, secondary;
while (! is_delimiter (next_token ()))
primary += token;
if (token == '%')
{
primary.erase ();
while (! is_delimiter (next_token ()))
primary += token;
}
if (token == '$')
while (! is_delimiter (next_token ()))
secondary += token;
entry.push_back (Entry (primary, secondary));
}
int main (int argc, char* argv[])
{
for (int document = 1; ; ++document)
{
if (next_token () == END_OF_FILE) break;
cout << "DOCUMENT " << document;
page = 1;
entry.clear ();
entry.push_back (Entry ("", ""));
do {
if (token == '&')
++page;
else if (token == '{')
add_entry ();
} while (next_token () != END_OF_DOCUMENT);
sort (entry.begin (), entry.end (), less_than);
for (int i = 1; i < entry.size(); ++i)
{
if (entry[i].primary == entry[i-1].primary)
if (entry[i].secondary == entry[i-1].secondary)
{
if (entry[i].page != entry[i-1].page)
cout << ", " << entry[i].page;
}
else
cout << "\n+ " << entry[i].secondary
<< ", " << entry[i].page;
else
{
cout << '\n' << entry[i].primary;
if (entry[i].secondary == "")
cout << ", " << entry[i].page;
else
cout << "\n+ " << entry[i].secondary
<< ", " << entry[i].page;
}
}
cout << endl;
}
}