/*
 * John W. Clark
 *
 * sample stl problem for acm presentation
 *
 * this is an indirect ( pointer ) implimentation
 *
 * DISCLAIMER : I am in no way endorsing a candidate or party
 * the sample numbers I used were pulled off the web
 * at around 1:30 am on Wed 11-3-04 and do reflect anything
 */

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;

typedef pair< string, pair< int, int > > arg;
typedef vector< arg * > storage;
typedef storage::iterator iter;
typedef storage::const_iterator citer;
typedef pair< citer, citer > pciter;

static const int indent[] = { 20, 15, 15 };

ostream & operator << ( ostream & ost, const arg & a )
{
    ost << setw(indent[0]) << left << a.first << right
        << setw(indent[1]) << a.second.first
        << setw(indent[2]) << a.second.second;
    return ost;
}

ostream & operator << ( ostream & ost, const pciter & p )
{
    for ( citer i = p.first; i != p.second ; ++i )
        ost << **i << endl;
    return ost;
}

ostream & operator << ( ostream & ost, const storage & s )
{
    ost << setw(indent[0]) << left << "state" << right 
        << setw(indent[1]) << "republican"
        << setw(indent[2]) << "democrat"
        << endl;
    for ( citer i = s.begin(); i != s.end() ; ++i )
        ost << **i << endl;
    return ost;
}

bool ptr_less ( const arg * l, const arg * r )
{
    return *l < *r;
}

bool rep_states ( storage::value_type & foo )
{
    return ( foo->second.second < foo->second.first );
}

int main()
{
    storage store;
    string line;
    char ch;
    // all valid input lines are of the form
    // state name republican_votes democrat_votes
    string state;
    int rep, dem;
    while ( cin.get(ch) )
    {
        if ( isdigit( ch ) )
        {
            cin.putback(ch);
            if ( cin >> rep >> dem )
                store.push_back( new arg ( state, make_pair( rep, dem )));
            else
                cerr << "invalid input" << endl;
        }
        else if ( ch == '\n' )
        {
            state = "";             // reset the state name
        }
        else
        {
            state += ch;
        }
    }

    sort( store.begin(), store.end(), ptr_less );
    cout << "all states" << endl;
    cout << store << endl;

    // partition by which part won
    iter rep_end = partition ( store.begin(), store.end(), rep_states );
    // sort the two partitions
    sort( store.begin(), rep_end, ptr_less );
    pciter e ( store.begin(), rep_end );
    sort( rep_end, store.end(), ptr_less );
    pciter d ( rep_end, store.end() );
    // output them
    cout << "Republican party" << endl;
    cout << e << endl;
    cout << "Democratic party" << endl;
    cout << d << endl;

    // total the votes
    pair< int, int > votes(0,0);
    for ( citer i = store.begin() ; i != store.end() ; ++i )
    {
        votes.first += (*i)->second.first;
        votes.second += (*i)->second.second;
    }
    cout << setw(indent[0]) << left << "total" << right
        << setw(indent[1]) << votes.first
        << setw(indent[2]) << votes.second
        << endl;

    // clean up that memory
    for ( citer i = store.begin() ; i != store.end() ; ++i )
        delete *i;

    return 0;
}