Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
快排手写,为啥超时???#include <cstdio> #include <iostream> #include <string.h> using namespace std; const int N = 51000; int n, m = 0; char dir[N][200]; int ind[N]; /* intdex of dir[] */ int num; /* 函数 */ void Init() { num = 0; } int Partition( int l, int r ) { int k = l; while( l < r ) { while( l < r ) { if( ::strcmp(dir[ ind[r] ], dir[ ind[k] ]) < 0 ) /* ind[r] <-> ind[k] */ { int temp = ind[r]; ind[r] = ind[k]; ind[k] = temp; k = r; break; } -- r; } while( l < r ) { if( ::strcmp(dir[ ind[l] ], dir[ ind[k] ]) > 0 ) /* ind[l] <-> ind[k] */ { int temp = ind[l]; ind[l] = ind[k]; ind[k] = temp; k = l; break; } ++ l; } } return k; } void qsort( int l, int r ) { if( l >= r ) return; int k = ::Partition( l, r ); ::qsort( l, k - 1 ); ::qsort( k + 1, r ); } bool BinSearch( int l, int r, const char* s ) { while( l <= r ) { int mid = ( l + r ) >> 1; int res = ::strcmp(dir[ ind[mid] ], s); if( res == 0 ) return 1; else if( res > 0 ) r = mid - 1; else l = mid + 1; } return 0; } void CheckSpelling() { scanf( "%d", & m ); for( int i = 1; i <= m; ++ i ) { ::Init(); char wrd[105] = {0}; scanf( "%s", wrd ); while( ::strcmp(wrd, "-1") != 0 ) /* check spelling for an email */ { if( !::BinSearch( 0, n - 1, wrd ) ) { ++ num; if( num == 1 ) printf( "Email %d is not spelled correctly.\n", i ); printf( "%s\n", wrd ); } scanf( "%s", wrd ); } if( num == 0 ) /* all correct */ { printf( "Email %d is spelled correctly.\n", i ); } } printf( "End of Output\n" ); } int main() { /* input directory */ scanf( "%d", & n ); for( int i = 0; i < n; ++ i ) { scanf( "%s", dir[i] ); } /* sort directory */ for( int i = 0; i < N; ++ i ) ind[i] = i; ::qsort( 0, n - 1 ); /* input email, and check spelling */ ::CheckSpelling(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator