#P3523. [Poi2014]Bricks

    ID: 2733 传统题 1000ms 128MiB 尝试: 411 已通过: 133 难度: 6 上传者: 标签>难度分类提高贪心堆贪心数据结构二叉堆构造与建模序列构造CF2000ByDzy

[Poi2014]Bricks

[POI2014] Bricks

题目描述

小朋友 Bitek 和同伴把各种颜色的积木排成一列,保证相邻积木颜色不同。第二天,Bitek 不小心把这排积木撞散了。他整理出各颜色的积木数量,还记得原来两端的颜色。

请用上全部积木,使相邻两块颜色不同,且第一块的颜色为 ss、最后一块的颜色为 tt。如果无法满足这些条件,请报告无解。

输入格式

第一行有三个整数 n,s,tn,s,t,分别表示颜色数、第一块积木要求的颜色、最后一块积木要求的颜色。

第二行有 nn 个整数 a1,…,ana_1,\ldots,a_n,其中 aia_i 表示颜色 ii 的积木数量。

输出格式

设 m=∑i=1naim=\sum_{i=1}^n a_i。如果有解,输出一行 mm 个空格分隔的整数,表示从左到右的颜色。若有多个解,输出任意一个。如果无解,仅输出一个整数 00。

样例 #1

3 3 1
2 3 3
3 2 1 3 2 3 2 1

另一种有效排列是 3 1 2 3 2 3 2 1。

样例 #2

3 3 1
2 4 2
0

数据范围

1≤n,m≤1061\le n,m\le10^6,1≤s,t≤n1\le s,t\le n,1≤ai≤1061\le a_i\le10^6。