题解 【WR2-1C】【「Wdoi-2」魔力的雷云】

· · 题解

题解

考虑每个 d_i 到底可以给我们提供多少信息。具体而言，从左往右考虑每一块磁铁。每次选择三块磁铁进行讨论。

情况一：\boxed\to\boxed\to\boxed\to

此时完全无法推断第二块和第三块磁铁的磁力大小，直接忽略。

情况二：\boxed\to\boxed\to\boxed\gets

做差，发现 x-y-1=b-a。可以直接推断出第一块和第二块磁铁的磁力大小。

情况三：\boxed\to\boxed\gets\boxed\gets

做差，发现 x-y-1=b-c。可以直接推断出第二块和第三块磁铁的磁力大小。

情况四：\boxed\to\boxed\gets\boxed\to

做差，发现 x-y-1=a+2b+c。感觉不一定有用阿。但是只要我们知道了 a 或者 c 的大小，就可以计算出剩余磁铁的磁力大小。

但是从这些地方，我们可以发现一些结论：

接着是特殊情况的讨论：

初始时设第一块磁铁方向向左即可。容易发现这不会对结果产生任何影响。不过有可能出现第一块磁铁左右两侧恰好有一块方向和它不同，你却不知道是哪个。那也问题不大，对两种情况分别求解判断合法性即可。

如何判断连续段的长度：

读者可以自行证明。这里不再赘述。

如何根据 a+2b,a\neq b 知晓 a 和 b 的值：

如何根据 a-b,a\neq b 知晓 a 和 b 的值：

读者可以自行验证/证明，这里不再赘述。

代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef unsigned int       u32;
typedef unsigned long long u64;
typedef long long i64;
const int INF =2147483647;
const int MAXN=1e6+3;
i64 D[MAXN],E[MAXN],A[MAXN]; bool F[MAXN]; int n,O[MAXN];
i64 qread(){
    i64 w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
i64 lowbit(i64 t){return t&-t;}
int countz(i64 t){return __builtin_ctzll(t);}
bool check(){
    A[0]=A[n],F[0]=F[n],A[n+1]=A[1],F[n+1]=F[1];
    i64 d0=n,d1=0,dn=0,dx=0;
    up(1,n,i){
        if(A[i]==-1) continue;
        if(A[i]!=(1ll<<(O[i]<<1))) return false;
        if(A[i]==A[i==1?n:i-1]||A[i]==A[i==n?1:i+1])
            return false;
    }
    up(1,n,i) if(F[i]!=F[i+1]) d0+=A[i]+A[i+1];
    if(d0!=D[0]) return false;
    up(1,n,i){
        dx=d0-1;
        if(F[i  ]!=F[i-1]) dx-=A[i  ]+A[i-1];
        if(F[i  ]!=F[i+1]) dx-=A[i  ]+A[i+1];
        if(F[i-1]!=F[i+1]) dx+=A[i-1]+A[i+1];
        if(dx!=D[i]) return false;
    }
    return true;
}
void find_add(i64 w,i64 &p,i64 &q){ // w=p+2q -> p,q
    i64 a=lowbit(w),b=w-a;
    if(countz(a)&1) q=a/2,p=b; else q=b/2,p=a;
}
void find_min(i64 w,i64 &p,i64 &q){ // w=p- q -> p,q
    if(w>0) q=lowbit( w),p=w+q;
    else    p=lowbit(-w),q=p-w;
}
int N[MAXN],M[MAXN];
void maintain1(){
    up(1,n,i) if(A[i]!=-2&&A[i]!=-1){
            int a=i,b=N[a],c=N[b];
            if(F[a]!=F[b]&&F[a]==F[c]){
                find_add(D[0]-D[b]-A[a]-1,A[c],A[b]);
            }
        }
}
void maintain2(){
    up(1,n,i){
        if(A[i]==-1) O[i]=114514+i; else O[i]=countz(A[i])/2;
    }
}
void showshowway(){
    up(1,n,i){
        printf("%lld, %d\n",A[i],F[i]);
    }
}
bool solve2(){
    up(1,n,i) N[i]=i+1; N[n]=1;
    up(1,n,i) M[i]=i-1; M[1]=n;
    up(2,n,i){
        if(  D[0]-D[i]        ==1) F[i+1]= F[i  ]; else
        if(((D[0]-D[i])%3+3)%3==1) F[i+1]=!F[i-1]; else
        if(((D[0]-D[i])%3+3)%3==2) F[i+1]=!F[i  ];
    }
    F[0]=F[n],F[n+1]=F[1]; bool g=0,h=0;
    up(1,n,i) g|=F[i],h|=F[i]==F[i+1];
    if(g==0){
        up(1,n,i) A[i]=-1; maintain2(); return check();
    } else if(h==0){
        i64 w=D[0]-D[1]-1;
        up(0,20,i){
            bool f=false;
            up(0,20,j){
                up(0,20,k){
                    i64 a=1ll<<(j<<1);
                    i64 b=1ll<<(i<<1);
                    i64 c=1ll<<(k<<1);
                    if(w==a+2*b+c) f=true;
                }
            }
            if(f){
                A[1]=(1ll<<(i<<1));
                maintain1(),maintain1(),maintain2();
                if(check()) return true;
            }
        }
    } else {
        up(1,n,i) if(F[i]!=F[M[i]]){
            int l=i,r=i,p=i;
            for(;F[r]==F[N[r]];r=N[r]); if(l==r) continue;
            find_min(D[0]-D[r]-1,A[r],A[M[r]]);
            find_min(D[0]-D[l]-1,A[l],A[N[l]]);
            for(;F[p]==F[N[p]];p=N[p]) if(A[p]==-2) A[p]=-1;
            if(l<r) i=r; else break;
        }
        maintain1(),maintain1(),maintain2();
        return check();
    }
    return 0;
}
void solve1(bool f){
    up(1,n,i) A[i]=-2,F[i]=-1; F[1]=false,F[2]=f;
    if(solve2()){
        up(1,n,i) printf("%d %d\n",F[i],O[i]); exit(0);
    }
}
i64 p1,p2,q1,q2;
int main(){
    n=qread(); up(0,n,i) D[i]=qread();
    if(n==1){puts("1");exit(0);}
    F[1]=false;
    if(  D[0]-D[1]        ==1)              solve1(false); else
    if(((D[0]-D[1])%3+3)%3==1) solve1(true),solve1(false); else
    if(((D[0]-D[1])%3+3)%3==2) solve1(true)              ;
    return 0;
}