2886.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2886  User Id:fzk 
Memory:15908K  Time:3370MS
Language:C++  Result:Accepted

Source 

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <iterator>
#include <memory.h>

using namespace std;

int tree[500100*4];
int n;

void init( int l, int r, int s ) {
	tree[s] = r-l;
	if( r > l+1 ) {
		int c = (l+r)/2;
		init( l, c, s*2 );
		init( c, r, s*2+1 );
	}
}

void set( int l, int r, int s, int k ) {
	int c = (l+r)/2;
	
	tree[s]--;
	
	if( r == l+1 )
		return;
	else if( k < c )
		set( l, c, s*2, k );
	else
		set( c, r, s*2+1, k );
}

int id;
void find( int l, int r, int s, int count ) {
	int c = (l+r)/2;
	
	if( r == l+1 )
		id = l;
	else if( tree[s*2] >= count )
		find( l, c, s*2, count );
	else
		find( c, r, s*2+1, count-tree[s*2] );
		
}

int p[500100], s[500100];
void clac_point( ) {
	int i, j, h, c;
	
	memset( p, 0, sizeof(p) );
	
	c = 1;
	for( i=2; c<500000; i++ ) {
		if( !p[i] ) {
			c++;
			for( j=i+i; j<=500000; j+=i )
				if( !p[j] )
					p[j] = i, c++;
		}
	}
	
	s[1] = 1;
	for( i=2; i<=500010; i++ ) {
		if( !p[i] )
			s[i] = 2;
		else {
			h = i;
			for( j=0; h%p[i]==0; h/=p[i], j++ )
				;
			s[i] = s[ h ]*(j+1);
		}
	}
}

char name[500010][12];
int num[500010];
int k;
bool input() {
	int i;
	if( scanf( "%d%d", &n, &k ) != 2 )
		return false;
	for( i=0; i<n; i++ ) 
		scanf( "%s%d", name[i], num+i );
	return true;
}

int main( ) {
	int i, m, best, k, j;
	
	clac_point( );
	
	while( input() ) {
		best = 1;
		for( i=2; i<=n; i++ )
			if( s[ best ] < s[ i ] )
				best = i;
				
		init( 0, n, 1 );
		k = ::k-1;
		j = ::k;
		m = n;
		for( i=1; i<best; i++ ) {
			set( 0, n, 1, k );
			m--;
			if( num[k] > 0 )
				j = (j-1+num[k]-1)%m+1;
			else {
				j = (j+num[k]-1)%m;
				if( j < 0 ) j+=m;
				j++;
			}
			find( 0, n, 1, j );
			k = id;
//			printf( "%s %d\n", name[k], j );
		}
		
		printf( "%s %d\n", name[k], s[best] );
	}
	return 0;
}