SRM479 Div2 Hard(1000) TheBoardingDivTwo

TheBoardingDivTwo

全通り試すだけ。後ろの乗客は、前の乗客が移動する時は移動できるけど、前の乗客が座る時は移動できない、ということに引っかかった。このために着席時間を75秒にするなら、制限時間も1秒増やす必要がある。

#include <vector>
#include <algorithm>

using namespace std;

class TheBoardingDivTwo
{
public:
    int find( vector <int> pattern, int boardingTime );
};

int TheBoardingDivTwo::find( vector <int> pattern, int boardingTime )
{
    int n = (int)pattern.size();

    int count = 0;

    vector<int> perm;
    for ( int i=1; i<=n; i++ )
        perm.push_back( i );

    do
    {
        bool f = true;
        for ( int i=0; i<n; i++ )
            if ( pattern[i] != -1  &&  pattern[i] != perm[i] )
                f = false;
        if ( ! f )
            continue;

        vector<int> cell( 2*n+1, 0 );
        for ( int i=1; i<=n; i++ )
            cell[i] = perm[i-1];
        vector<int> wait( n+1, 74+1 );

        for ( int t=0; t<boardingTime+1; t++ )
        {
            for ( int i=2*n; i>=1; i-- )
            if ( cell[i] != 0 )
            {
                if ( i < n + cell[i]  &&  cell[i+1] == 0 )
                    cell[i+1] = cell[i],
                    cell[i] = 0;
                if ( i == n + cell[i] )
                    if ( --wait[cell[i]] == 0 )
                        cell[i] = 0;
            }
        }

        f = true;
        for ( int i=1; i<=2*n; i++ )
            if ( cell[i] != 0 )
                f = false;
        if ( f )
            count++;
    }
    while ( next_permutation( perm.begin(), perm.end() ) );

    return count;
}