2013年9月28日 星期六

2013/9/24 HSNU OJ 88 - Lollipop

/* http://hoj.twbbs.org/judge/problem/view/88 */
#include <iostream>
#include <cstdio>

using namespace std;

char lol[1500000]; int pos[3000000], sum[1500000];
int N, M;
int MaxO, MaxE, NowO, NowE;

void Ans(int num)
{
    int Sum = sum[pos[num]];

    int l = -1, r = pos[num], mid;

    while( l+1 != r )
    {
        mid = (l+r)/2;
        if( Sum - sum[mid] >= num ) l = mid;
        else r = mid;
    }

    printf("%d %d\n", r, pos[num]);
}

int main()
{
    scanf("%d %d", &N, &M);
    scanf("%s", lol);

    for(int Ni = 0; Ni < N; Ni++)
    {
        if( lol[Ni] == 'T' )
        {
            if( NowE % 2 == 0 ){ NowE += 2;  }
            if( NowO % 2 == 1 ){ NowO += 2;  }
            sum[Ni+1] = sum[Ni]+2;
        }
        else
        {
            int PE, PO;
            if( NowE % 2 == 0 ){ PO = NowE+1; }
            else{ PO = 0; }
            if( NowO % 2 == 1 ){ PE = NowO+1; }
            else{ PE = 0; }

            NowE = PE; NowO = PO;
            sum[Ni+1] = sum[Ni]+1;
        }

        while( MaxE < NowE )
        {
            if( MaxE % 2 != 0 ) MaxE++;
            else MaxE += 2;
            pos[MaxE] = Ni+1;
        }

        while( MaxO < NowO )
        {
            if( MaxO % 2 != 1 ) MaxO++;
            else MaxO += 2;
            pos[MaxO] = Ni+1;
        }

    }

    for(int Mi = 0; Mi < M; Mi++)
    {
        int k; scanf("%d", &k);

        if( k % 2 == 0 && k > MaxE ) puts("NIE");
        else if( k % 2 == 1 && k > MaxO ) puts("NIE");
        else
        {
            Ans(k);
        }
    }
}

沒有留言:

張貼留言