SRM495 Div1 Easy(275), Div2 Medium(525) ColorfulCards

ColorfulCards

なるべく小さな数字を選んだとときと大きな数字を選んだときの数字が一致すればその数字、一致しなければ-1。

#include <string>
#include <vector>
using namespace std;

class ColorfulCards{public:
vector <int> theCards( int N, string colors )
{
    int n = (int)colors.size();
    string P(N+1,'R');
    P[1] = 'B';
    for ( int i=1; i<=N; i++ )
    if ( P[i] == 'R' )
        for ( int j=i+i; j<=N; j+=i )
            P[j] = 'B';

    vector<int> L(n), R(n);

    int p = 1;
    for ( int i=0; i<n; i++ )
    {
        while ( P[p] != colors[i] )
            p++;
        L[i] = p;
        p++;
    }

    p = N;
    for ( int i=n-1; i>=0; i-- )
    {
        while ( P[p] != colors[i] )
            p--;
        R[i] = p;
        p--;
    }

    vector<int> ans(n);
    for ( int i=0; i<n; i++ )
        ans[i] = L[i]==R[i] ? L[i] : -1;
    return ans;
}};