pku2886 Who Gets the Most Candies?

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;

#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
/************ for topcoder by zz1215 *******************/
#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FFF(i,a)        for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-9;
const double pi = acos(-1.0);
const int maxn = 500011;

struct zz
{
	int x;    // sum
	int l;
	int r;
}zx[maxn<<2];

struct ss
{
    int h;
    int x;
    bool operator < (const ss & cmp ) const
    {
        return x<cmp.x;
    }
}sd;

int n,k;
string s[maxn];
int f[maxn];
int oula[maxn];
vector<int>p;
vector<ss>fp;
vector<ss>vx;
int endpos;
int endans;

void pushup(int root)
{
	zx[root].x = zx[LL(root)].x + zx[RR(root)].x;
	return ;
}

void build(int l=1,int r=n,int root=1)
{
	zx[root].l = l;
	zx[root].r = r;
	if(l==r)
	{
		zx[root].x=1;
		return ;
	}
	else
	{
		int mid = (l+r)/2;
		build(l,mid,LL(root));
		build(mid+1,r,RR(root));
		pushup(root);
	}
	return ;
}

int query(int l,int r,int root=1)
{
	if(l<=zx[root].l && r>=zx[root].r)
	{
		return zx[root].x;
	}
	else
	{
		int re = 0;
		if(LL(root)<maxn*4 && l<=zx[LL(root)].r)
		{
			re += query(l,r,LL(root));
		}
		if(RR(root)<maxn*4 && r>=zx[RR(root)].l)
		{
			re += query(l,r,RR(root));
		}
		return re;
	}
}

void remove(int pos,int root=1)
{
	if(zx[root].l==pos && zx[root].r == pos)
	{
	//	assert(zx[root].x!=0);
		zx[root].x = 0;
		return ;
	}
	else
	{
		if(LL(root)<maxn*4 && pos<=zx[LL(root)].r)
		{
			remove(pos,LL(root));
		}
		else if(RR(root)<maxn*4 && pos>=zx[RR(root)].l)
		{
			remove(pos,RR(root));
		}
		pushup(root);
	}
	return ;
}

bool isp(int x)
{
    for(int i=0;p[i]*p[i]<=x;i++)
    {
        if(x%p[i]==0)
        {
            return false;
        }
    }
    return true;
}

void initp()
{
    p.clear();
    p.pb(2);
    for(int i=3;i<100;i++)
    {
        if(isp(i))
        {
            p.pb(i);
        }
    }
    return ;
}

void dfs(int rest,int step=0,int pre=inf,int have=1,int now=1)
{
    if(now>maxn || step >= p.size() ) return ;
    if(rest == 0)
    {
        sd.x=now;
        sd.h=have;
        vx.pb(sd);
        return ;
    }
    else
    {
        int temp;
        for(int i=min(rest,pre);i>=1;i--)
        {
            temp = now;
            for(int u=1;u<=i;u++)
            {
                temp*=p[step];
				if(temp>maxn) return ;
            }
            dfs(rest-i,step+1,i,have*(i+1),temp);
        }
    }
    return ;
}

void init()
{
	vx.clear();
	fp.clear();
	for(int i=0;i<30;i++)
    {
        dfs(i);
    }
    sort(vx.begin(),vx.end());
    int temp=-inf;
    for(int i=0;i<vx.size();i++)
    {
        if(vx[i].h>temp)
        {
            temp = vx[i].h;
            fp.pb(vx[i]);
        }
    }
	return ;
}

int find(int tx)
{
	int root = 1;
	while(zx[root].l!=zx[root].r)
	{
		if(zx[LL(root)].x>=tx)
		{
			root = LL(root);
		}
		else
		{
			tx-=zx[LL(root)].x;
			root =RR(root);
		}
	}
	return zx[root].l;
}

void start()
{
	build();
    for(int i=0;i<fp.size();i++)
    {
        if(n>=fp[i].x)
        {
            endpos = fp[i].x;
            endans = fp[i].h;
        }
        else
        {
            break;
        }
    }
    int now = k;
    int temp;
    int tot;
    for(int i=1;i<endpos;i++)
    {
        remove(now);
		tot=zx[1].x;
		if(f[now]>0)
		{
			temp = query(1,now) + f[now];
			temp = (temp-1)%tot+1;
			temp = (temp+tot-1)%tot+1;
		}
		else
		{
			temp = query(1,now) + 1 + f[now];
			temp = (temp-1)%tot+1;
			temp = (temp+tot-1)%tot+1;
		}
		now = find(temp);
    }
    endpos = now;
	return ;
}

int main()
{
	initp();
	init();
	char c[15];
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%s",c);
			s[i] = c;
			SS(f[i]);
		}
        start();
        cout<<s[endpos]<<" "<<endans<<endl;
	}
	return 0;
}