PKU 1025 Department

Department

複雑だけど問題文の通りに書くだけ。１秒ごとにシミュレートしても間に合う。エレベータを特殊な部屋とみなしたり入退室の処理は固定時間なので省いたりして多少はコードがすっきりした。

出力はエージェントのコード順にソートするように指示されているけど入力はソートされていないので、自前でソートしないとWrong Answerになる。なんといやらしいテストデータ。

#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

//  部屋番号xx00はxx階のエレベーター
//  部屋番号0199は受付

enum STATE
{
    INITIAL,    //  未到着
    TRANSFER,   //  同じフロアの移動中
    INQUEUE,    //  順番待ち
    INROOM,     //  部屋・エレベーターの中
    END,        //  退館
};

struct AGENT
{
    char            code;       //  コード
    int             enter;      //  到着時刻
    vector<int>     room;       //  i番目の部屋
    vector<int>     stay;       //  ↑の滞在時間

    STATE           state;      //  現在の状態
    int             pos;        //  現在位置（移動中は移動元）
    int             rest;       //  現在の行動の残り時間

    vector<int>     end;        //  添字の行動を終えた時刻
    vector<string>  activity;   //  行動内容

    bool operator<( const AGENT a ) const { return code < a.code; }
};

typedef vector<AGENT>::iterator iter;

//  部屋番号を文字列に
string roomstr( int r )
{
    if ( r % 100 == 0 )
        return "elevator";
    else
    {
        char b[16];
        sprintf( b, "room %04d", r );
        return b;
    }
}

int main()
{
    //  入力
    vector<AGENT> agent;

    while ( true )
    {
        AGENT a;
        scanf( " %c", &a.code );
        if ( a.code == '.' )  break;

        int h, m, s;  scanf( "%d:%d:%d", &h, &m, &s );
        a.enter = ( h * 60 + m ) * 60 + s;

        while ( true )
        {
            int r;  scanf( "%d", &r );
            if ( r == 0 )  break;
            a.room.push_back( r );

            int t;  scanf( "%d", &t );
            a.stay.push_back( t );
        }
        //  最後に受付に行く
        a.room.push_back( 199 );
        a.stay.push_back( 0 );

        agent.push_back( a );
    }

    sort( agent.begin(), agent.end() );

    //  シミュレート
    vector<iter>    queue[1100];            //  キュー
    bool            room[1100] = { false }; //  添字の部屋に人がいれば真

    for ( iter a=agent.begin(); a!=agent.end(); a++ )
        a->state = INITIAL;

    for ( int t=0; ; t++ )
    {
        //printf( "t = %d\n", t );
        //for ( iter a=agent.begin(); a!=agent.end(); a++ )
        //  printf( "%c %d %d %d\n", a->code, a->state, a->pos, a->rest );

        //  全員退館したら終了
        bool end = true;
        for ( iter a=agent.begin(); a!=agent.end(); a++ )
            if ( a->state != END )
                end = false;
        if ( end )
            break;

        //  エージェントを動かす
        for ( iter a=agent.begin(); a!=agent.end(); a++ )
        if ( a->state != END )
        {
            //  到着時刻+30になったら入館
            if ( a->state == INITIAL  &&
                 a->enter+30 <= t )
            {
                a->end.push_back( t );
                a->activity.push_back( "Entry" );

                a->state = INQUEUE;
                int r = a->room[0];
                queue[r/100==1?r:100].push_back( a );               
                continue;
            }

            //  残り時間が0
            if ( --a->rest <= 0 )
            switch ( a->state )
            {
            //  移動中だったならキューへ
            case TRANSFER:
                int r;
                if ( a->room[0]/100 == a->pos/100 )
                    r = a->room[0];     //  目的の部屋へ
                else
                    r = a->pos/100*100; //  エレベーターへ

                a->state = INQUEUE;
                queue[r].push_back( a );

                a->end.push_back( t );
                a->activity.push_back( "Transfer from " + roomstr(a->pos) +
                                       " to " + roomstr(r) );
                break;

            //  部屋・エレベーターの中だったなら移動を開始
            case INROOM:
                if ( a->pos % 100 != 0 )
                    room[a->pos] = false;
                
                a->state = TRANSFER;
                a->rest = 10;

                if ( a->pos % 100 == 0 )
                    a->pos = a->room[0]/100*100;    //  目的の階へ

                a->end.push_back( t );
                a->activity.push_back( "Stay in "+roomstr(a->pos) );
                break;
            }
        }

        //  キューの処理
        //  受付
        while ( ! queue[199].empty() )
            queue[199][0]->state = END,
            queue[199].erase( queue[199].begin() );

        for ( int f=1; f<=10; f++ )
        for ( int i=f*100; i<=f*100+10; i++ )
        if ( ! queue[i].empty() )
        {
            //  エレベーター・部屋
            if ( i % 100 == 0  &&  t % 5 == 0  ||   //  エレベーター（５秒ごと）
                 i % 100 != 0  &&  ! room[i] )      //  部屋（空いていれば）
            {
                //  先頭のエージェント
                int an = 0;
                iter a = queue[i][0];
                for ( int j=1; j<(int)queue[i].size(); j++ )
                    if ( queue[i][j]->code < a->code )
                        a = queue[i][j],
                        an = j;
                

                a->state = INROOM;
                a->pos = i;
                if ( i % 100 == 0 )
                    a->rest = abs(a->pos/100-a->room[0]/100) * 30;
                else
                    a->rest = a->stay[0];

                if ( i % 100 != 0 )
                {
                    room[i] = true;
                    a->room.erase( a->room.begin() ),
                    a->stay.erase( a->stay.begin() );
                }

                //  待ち時間があった場合のみログ記録
                if ( a->end.back() < t )
                {
                    a->end.push_back( t );
                    if ( i % 100 == 0 )
                        a->activity.push_back( "Waiting in elevator queue" );
                    else
                        a->activity.push_back( "Waiting in front of "+roomstr(i) );
                }
                
                queue[i].erase( queue[i].begin() + an );
            }
        }
    }

    for ( iter a=agent.begin(); a!=agent.end(); a++ )
    {
        //  １階の移動を削除して、受付を追加
        a->end.pop_back();
        a->activity.pop_back();

        a->end.push_back( a->end.back() + 30 );
        a->activity.push_back( "Exit" );
    }

    //  行動ログを表示
    for ( iter a=agent.begin(); a!=agent.end(); a++ )
    {
        printf( "%c\n", a->code );

        int s = a->enter;
        for ( int i=0; i<(int)a->end.size(); i++ )
        {
            int e = a->end[i];
            printf( "%02d:%02d:%02d %02d:%02d:%02d %s\n",
                    s/3600, s/60%60, s%60,
                    e/3600, e/60%60, e%60,
                    a->activity[i].c_str() );
            s = e;
        }
        printf( "\n" );
    }

    return 0;
}