CodeForces 238B

同时也是 LETTers 2015 Summer II round 01 - D

#include <cstdio>
#include <iostream>
#include <algorithm>

#define lld I64d

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL s[N];

int main()
{
    int n;
    LL h;

    //freopen("D.in", "r", stdin);
    scanf("%d%lld", &n, &h);
    scanf("%d", &s[0]);
    int t = s[0], index = 0;
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &s[i]);
        if (s[i] < t)
        {
            t = s[i];
            index = i;
        }
    }

    sort(s, s+n);
    LL maxsum = max(s[n-1]+s[n-2], s[n-1]+s[0]+h);
    LL minsum = min(s[0]+s[1]+h, s[1]+s[2]);
    LL rec1 = maxsum - minsum;
    LL rec2 = s[n-1]+s[n-2]-(s[0]+s[1]);
    if (rec1 < rec2)
    {
        printf("%lld\n", rec1);
        for (int i = 0; i < n - 1; i++)
        {
            if (i != index)
            {
                printf("1 ");
            }
            else
            {
                printf("2 ");
            }
        }

        if (n - 1 != index)
        {
            printf("1\n");
        }
        else
        {
            printf("2\n");
        }
    }
    else
    {
        printf("%lld\n", rec2);
        for (int i = 0; i < n - 1; i++)
        {
            printf("1 ");
        }
        printf("1\n");
    }


    return 0;
}