1880.cpp

ACM比赛解题报告,包括hdu1880、zoj1010、zoj1015

#include<iostream>
#include<string>
#include<vector>
#include<cstdlib>
using namespace std;

#define NLEN 150
#define MLEN 300

struct Word
{
	string name;
	string mean;
};

vector<Word> list;

int nOrder[ 100005 ], nSize;
int mOrder[ 100005 ], mSize;

int cmp1( const void *a, const void *b )
{
	int x = *(int*)a;
	int y = *(int*)b;
	return strcmp( list[ x ].name.c_str(), list[ y ].name.c_str() );
}

int cmp2( const void *a, const void *b )
{
	int x = *(int*)a;
	int y = *(int*)b;
	return strcmp( list[ x ].mean.c_str(), list[ y ].mean.c_str() );
}

int T;

void setOrder()
{
	nSize = mSize = list.size();
	for ( int i = 0; i < list.size(); i ++ )
		nOrder[ i ] = mOrder[ i ] = i;
	
	qsort( nOrder, nSize, sizeof( int ), cmp1 );
	qsort( mOrder, mSize, sizeof( int ), cmp2 );
}

void readDic()
{
	list.clear();
	
	Word tmp;
	const int BUFLEN = 1005;
	char buffer[ BUFLEN ];
	char name[ BUFLEN ];
	
	while ( gets( buffer ) != NULL && strcmp( buffer, "@END@" ) != 0 )
	{
		int i = 0, idx = 0;
		while( buffer[ i ] != '[' ) i ++;
		while ( buffer[ i ] != ']' )
			name[ idx ++ ] = buffer[ i ++ ];
		name[ idx ++ ] = ']';
		name[ idx ] = '\0';
		tmp.name = name;
		i += 2;
		
		strcpy( name, buffer + i );
		tmp.mean = name;
		
		list.push_back( tmp );
	}
}

bool bSearch( char ch, string key )
{
	int begin = 0, end = list.size() - 1;
	
	while ( begin <= end )
	{
		int mid = ( begin + end ) / 2;
		int pos;
		if ( ch == 'n' )
		{
			pos = nOrder[ mid ];
			if ( key < list[ pos ].name )
				end = mid - 1;
			else if ( key > list[ pos ].name )
				begin = mid + 1;
			else
			{
				cout << list[ pos ].mean << endl;
				return true;
			}
		}
		else if ( ch == 'm' )
		{
			pos = mOrder[ mid ];
			if ( key < list[ pos ].mean )
				end = mid - 1;
			else if ( key > list[ pos ].mean )
				begin = mid + 1;
			else 
			{
				for ( int i = 1; i < list[ pos ].name.length() - 1; i ++ )
					cout << list[ pos ].name[ i ];
				cout << endl;
				
				return true;
			}
		}
	}
	
	return false;
}

void solve()
{
	scanf( "%d", &T );
	getchar();
	char buffer[ 1000 ];
	while ( T -- )
	{
		gets( buffer );
		string str = buffer;
		if ( buffer[ 0 ] == '[' )
		{
			if ( !bSearch( 'n',  str ) )
				cout << "what?" << endl;
		}
		else
		{
			if ( !bSearch( 'm', str ) )
				cout << "what?" << endl;
		}
	}
}

int main()
{
	readDic();
	setOrder();
	solve();
	
	return 0;
}