2015年3月24日 星期二

2015/03/24 POI 21th Bricks

/*
    greedy
    先取能取的當中數量最多的
    數量一樣 就取和最後一個顏色一樣的
*/
// http://main.edu.pl/en/archive/oi/21/klo
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int K, P, Q;

struct AI
{
    int a, i;
    AI(){}
    AI(int _a, int _i):a(_a),i(_i){}

    bool operator<(const AI& p)const
    {
        return p.a > a || p.a == a && p.i == Q;
    }
};

priority_queue<AI> pri;

int Ans[2000000];
int cnt[2000000];

int N = 0;

int main()
{
    scanf("%d %d %d", &K, &P, &Q);

    bool OK = true;

    for(int Ki = 1; Ki <= K; Ki++)
    {
        scanf("%d", &cnt[Ki]);
        N += cnt[Ki];

        if( Ki == P ) cnt[Ki]--;
        if( Ki == Q ) cnt[Ki]--;

        if( cnt[Ki] > 0 ) pri.push(AI(cnt[Ki], Ki) );
        if( cnt[Ki] < 0 ) OK = false;
    }

    if( N == 1 ) OK = true;

    Ans[0] = P;
    Ans[N-1] = Q;

    for(int Ni = 1; Ni < N-1; Ni++)
    {
        AI t = pri.top();
        pri.pop();

        if( t.i == Ans[Ni-1] )
        {
            if( !pri.empty() )
            {
                AI p = pri.top();
                pri.pop();

                pri.push(t);
                t = p;
            }
        }

        Ans[Ni] = t.i;

        if( t.a-1 ) pri.push(AI(t.a-1, t.i) );
    }

    for(int Ni = 1; Ni < N; Ni++)
        if( Ans[Ni] == Ans[Ni-1] ) OK = false;

    if( !OK ) puts("0");
    else
    {
        for(int Ni = 0; Ni < N; Ni++)
        {
            printf("%d", Ans[Ni]);

            if( Ni != N-1 ) printf(" ");
            else puts("");
        }
    }
}

沒有留言:

張貼留言