Good Bye 2018 Codeforces 1091E New Year and the Acquaintance Estimation

链接：https://codeforces.com/contest/1091/problem/E

先说一下这题在考场怎么AC吧。。
仔细观察一下题面，发现有一个链接

点进去，可以到达这么一个页面

你会发现，假设我们枚举了n+1的度数是什么，那么这个问题就是我们要解决的
接着你可以发现有一个Solutions

仔细阅读，发现第二个的用处是判断是否可行，因此直接点进第二个
如果第一个判断是否可行的复杂度比第二个还优秀，那么第二个就没有放在这里的必要了。。

于是就可以找到判断的公式了。。

如果事先排序，然后插入一个数
那么整个过程就可以在$O(n)$时间解决了

考虑优化。。枚举实在是太慢了
先知道奇偶性
直接猜想，一定是连续的一段奇数/偶数
那么，假设我们可以知道一个解，剩下就可以二分了
问题转化为如何求出一个解
考虑继续二分，问题转化为二分的值是大了还是小了
我们发现，如果我们插入的数，在枚举到的k之后，那么显然是小了
否则，那么就是大了

至此，问题已经解决
时间复杂度是$O(nlogn)$的

那么剩下，用中文给大家说一下那两个方法是什么（当然都没有严谨的证明）
判断可行的，就是按照d从大往小枚举，假设有任何一个k不符合上式，那么就是没有，否则就是有

另外一个，是可以输出方案的
依然从大到小排序，假设一个序列$d_1,d_2,d_3....d_n$合法，那么$d_2?1,d_3?1,d_4?1....d_{d_1}?1,d_{d_1+1},,d_{d_1+2}....d_n$合法
不断递归，假设都是0，那么就合法了
假设过程中出现了负数，那么就不合法
也就是度数最大的点找度数较大的点连边

附上本题代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=500005;
LL n,sum;
LL d[N];
LL h[N];
LL du[N];
bool cmp (LL x,LL y)	{
    return x>y;}
LL check (LL x)//合法:0 在前面不合法:1 在后面不合法:2 
{
    bool tf=false;LL tot=0;for (LL u=1;u<=n;u++){
    if (tf==false&&x>=d[u]) 	{
    tf=true;du[++tot]=x;}du[++tot]=d[u];}if (tf==false) du[++tot]=x;h[tot+1]=0;for (LL u=tot;u>=1;u--)	h[u]=h[u+1]+du[u];LL i=tot,now=0;for (LL u=1;u<=tot;u++){
    i=max(i,u+1);while (i>(u+1)&&du[i-1]<=u) i--;now=now+du[u];if (now>u*(u-1)+(i-(u+1))*u+h[i]){
    if (d[u]<=x) return 1;else return 2;}}return 0;
}
LL t[N],m;
int main()
{
    scanf("%I64d",&n);for (LL u=1;u<=n;u++) {
    scanf("%I64d",&d[u]);sum=sum+d[u];}sort(d+1,d+1+n,cmp);if (sum&1){
    for (LL u=1;u<=n;u+=2)	t[++m]=u;}else{
    for (LL u=0;u<=n;u+=2) t[++m]=u;}LL l=1,r=m,L,R;LL xx=-1;while (l<=r){
    LL mid=(l+r)>>1;if (check(t[mid])==0)  {
    xx=mid;break;}else if (check(t[mid])==1) r=mid-1;else l=mid+1;}if (xx==-1)	{
    printf("-1\n");return 0;}l=1,r=xx;while (l<=r){
    LL mid=(l+r)>>1;if (check(t[mid])==0) {
    L=mid;r=mid-1;}else l=mid+1;}l=xx;r=m;while (l<=r){
    LL mid=(l+r)>>1;if (check(t[mid])==0) {
    l=mid+1;R=mid;}else r=mid-1;}for (LL u=L;u<=R;u++) printf("%I64d ",t[u]);return 0;
}