JAPLJ Contest C Cosmos

Cosmos

線分で分割されたグループ内で白とピンクのコスモスが同じ数になるように線分を結んでいけば良い。単純に実装すると50点。予めp番目までで白いコスモスが何本多いかを計算しておいて計算量を線形にすれば100点。けっこう制限時間が厳しい気がする。queue使ったら通らなかった。

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

int main()
{
    int n;  cin >> n;
    vector<char> S( 2*n+1 );
    scanf( "%s", &S[0] );
    
    vector<vector<int> > _T( 2*n+1 );
    vector<int> *T = &_T[n];
    int t = 0;
    for ( int i=2*n-1; i>=0; i-- )
    {
        T[t].push_back( i );
        t += S[i]=='W' ? -1 : 1;
    }

    vector<int> ans( 2*n, -1 );
    
    t = 0;
    for ( int i=0; i<2*n; i++ )
    {
        if ( ans[i] == -1 )
            ans[i] = T[t].back(),
            ans[ans[i]] = i;

        t += S[i]=='W' ? 1 : -1;
        T[t].pop_back();
    }

    for ( int i=0; i<2*n; i++ )
        printf( "%d\n", ans[i]+1 );
}