Source Code

Problem: 2886  User: jibee 
Memory: N/A  Time: N/A 
Language: C++  Result: Wrong Answer 

Source Code 
#include <iostream>
#include <cmath>
#include <fstream>
using std::cout;
using std::endl;
using std::ifstream;
using std::cin;

//

const int MAXLENGTH = 12;
const int MAXNUM = 500001;
const int ITEMNUM = 37;


struct Node{
	int left;
	int right;
	int idx;  // 0 represent internal node
};

char name[MAXNUM][MAXLENGTH];
int turn[MAXNUM];

Node* child;
int (*tableItem)[2];

int n;
int curN;
int nameStart;
int totalFloor;
int targetItemIdx;
int curTurn;

int buildIdx;

void build( int node, int num ){
	if( num <= 0 ) return;
	if( num == 1 ){
                    child[node].left = 0;
                    child[node].right = 0;
		child[node].idx = ++buildIdx;
		return;
	}
	int m = num / 2;
	child[node].left = m;
	child[node].right = num - child[node].left;
	child[node].idx = 0;
	build( node * 2, child[node].left );
	build( node * 2 + 1, child[node].right );
	return;
}

int pick( int localTurn, int node ){
	if( child[node].idx != 0 ){
		curN --;
		if( n - curN == tableItem[targetItemIdx][0] ) {
			cout << name[child[node].idx] << ' ' << tableItem[targetItemIdx][1] << endl;
			return 0;
		}
		else{
			if( turn[child[node].idx] > 0 ){
			    return (curTurn -2 + turn[child[node].idx]) % curN + 1 ;
			   
			}
			else{
				return curN  - (( curN - curTurn ) - turn[child[node].idx] ) % curN ;
				
			}
		}
	}
	else{
		if( child[node].left >= localTurn ){
			child[node].left--;
			return pick( localTurn, node * 2 );
		}
		else{
			child[node].right--;
			return pick( localTurn - child[node].left, node * 2 + 1 );
		}

	}
}




int main(){
	      //ifstream cin( "in.txt" );
          child = new Node[MAXNUM * 3];
           //clock_t start = clock();
          int theTableItem[ITEMNUM + 1][2] = { 1,1,2,2,4,3,6,4,12,6,24,8,36,9,48,10,60,12,
		                              120,16,180,18,240,20,360,24,720,30,840,32,
									   1260,36,1680,40,2520,48,5040,60,7560,64,
									   10080,72,15120,80,20160,84,25200,90,27720,96,
									   45360,100,50400,108,55440,120,83160,128,
									   110880,144,166320,160,221760,168,277200,180,
									   332640,192,498960,200, 554400,216, 665280, 224  };
	       tableItem = theTableItem;
          // cout << table[MAXNUM -1][0] << endl;
           //cout << "time_used:" << clock() - start << endl;
           int k;
           while( !cin.eof()){
			   cin >> n >> k;
			   //cin.ignore();
			   curN = n;
			   for( int i = 1; i <= n; i ++ ){
                                            cin >> name[i] >> turn[i];
                                 }
			   int l = -1;
			   int r = ITEMNUM + 1;
			   while( l != r -1 ){
				   int m = ( l + r )/ 2;
				   if( n >= tableItem[m][0] )
					   l = m;
				   else r = m;
			   }
			   targetItemIdx = l;
			   buildIdx = 0;
			   build( 1, n );
			   curTurn = k;
			   while( curTurn != 0 ){
			      curTurn = pick( curTurn, 1 );
			   }
           }
           delete []child;
           child = 0;
           //system( "pause" );
           return 0;
}