HDU : 3293 (sort)



// http://acm.hdu.edu.cn/showproblem.php?pid=3293

Notes :
1. straightforward problem

2. bubble sort works fine

3. take care about 10 spaces in output

4. input will terminate for end of file character 

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
using namespace std;

struct origin {
    char org [25];
    struct nameAndRank {
        char name [25];
        int rank;
    } nr [500 + 5];
    int len;
} a [500 + 5];

void reset ()
{
    for ( int i = 0; i < 505; i++ )
        a [i].len = 0;
}

bool cmp (origin x, origin y)
{
    if ( strcmp (x.org, y.org) < 0 ) return true;
    return false;
}

int main ()
{
    int n;
    int cases = 0;

    while ( scanf ("%d", &n) != EOF ) {
        getchar ();

        char input [1000];
        map <string, int> findIndex;
        int totalOrigin = 1;
        int index;

        reset ();

        for ( int i = 0; i < n; i++ ) {
            gets (input);
            char o [25], n [25], r [25];
            sscanf (input, "%s %s %s", n, o, r);

            int replacement;
            if ( strcmp (r, "wonderful") == 0 ) replacement = 0;
            else if ( strcmp (r, "good") == 0 ) replacement = 1;
            else  if ( strcmp (r, "so-so") == 0 ) replacement = 2;

            if ( findIndex [o] ) {
                index = findIndex [o];
                strcpy (a [index].nr [a [index].len].name, n);
                a [index].nr [a [index].len].rank = replacement;
                a [index].len++;
            }
            else {
                findIndex [o] = totalOrigin++;
                index = findIndex [o];
                strcpy (a [index].org, o);
                strcpy (a [index].nr [a [index].len].name, n);
                a [index].nr [a [index].len].rank = replacement;
                a [index].len++;
            }
        }

        sort (a + 1, a + totalOrigin, cmp);

        for ( int i = 1; i < totalOrigin; i++ ) {
            for ( int j = 0; j < a [i].len; j++ ) {
                for ( int k = j + 1; k < a [i].len; k++ ) {
                    if ( a [i].nr [j].rank > a [i].nr [k].rank )
                        swap (a [i].nr [j], a [i].nr [k]);
                    else if ( a [i].nr [j].rank == a [i].nr [k].rank && strcmp (a [i].nr [j].name, a [i].nr [k].name) > 0 )
                        swap (a [i].nr [j], a [i].nr [k]);
                }
            }
        }

        printf ("Case %d\n", ++cases);

        for ( int i = 1; i < totalOrigin; i++ ) {
            printf ("%s:\n", a [i].org );
            for ( int j = 0; j < a [i].len; j++ ) {
                printf ("          ");
                printf ("%s ", a [i].nr [j].name);
                if ( a [i].nr [j].rank == 0 ) printf ("wonderful\n");
                else if ( a [i].nr [j].rank == 1 ) printf ("good\n");
                else printf ("so-so\n");
            }
        }

    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s