题解 P6676 【[COCI2019-2020#2] Slagalica】

· · 题解

看懂题目后，我们可以发现我们需要判断当前这个拼图的种类是根据上一块拼图的种类而决定的。

如果上一块拼图的右边是凸进去的，那么我们就将有两个选择：3 号拼图和 4 号拼图。如果其中一种拼图用完了，那就用另外一种拼图呗。如果两种拼图都有，那么就看一下哪个编号小咯。但是选 4 号拼图的时候一个条件：得有 1 号拼图为它擦屁股；为什么呢？对于一开始凸的形状，如果最后不能还原成凸的形状，那么最后一块就无法装了。

如果上一块拼图的右边是凹进去的，那么我们就将有两个选择：1 号拼图和 2 号拼图。如果其中一种拼图用完了，那就用另外一种拼图呗。如果两种拼图都有，那么就看一下哪个编号小咯。但是选 1 号拼图的时候一个条件：得有 4 号拼图为它擦屁股。为什么呢？对于一开始凹的形状，如果最后不能还原成凹的形状，那么最后一块就无法装了。

还有一个问题：我们应该如何取每种拼图的最小编号呢？集合或者小根堆啊！

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,L,R,flg,cnt=1,hep[5][maxn],size[5],ans[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void put(int id,int x){
    hep[id][++size[id]]=x;int son=size[id];
    while(son>1&&hep[id][son]<hep[id][son/2])swap(hep[id][son],hep[id][son/2]),son/=2;
}
int get(int id){
    int x=hep[id][1];int fa=1,son;hep[id][1]=hep[id][size[id]--];
    while(fa*2<=size[id]){
        if(fa*2+1>size[id]||hep[id][fa*2]<hep[id][fa*2+1])son=fa*2;else son=fa*2+1;
        if(hep[id][son]<hep[id][fa])swap(hep[id][son],hep[id][fa]),fa=son;else break;
    }
    return x;

}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read(),w=read();
        if(x==5)ans[1]=w,L=0;
        else if(x==6)ans[1]=w,L=1;
        else if(x==7)flg=w,R=1;
        else if(x==8)flg=w,R=0;
        else put(x,w);
    }
    while(1){
        if(L){
            if(!size[1]&&!size[2])break;
            else if(size[1]&&!size[2])ans[++cnt]=get(1),L=1-L;
            else if(!size[1]&&size[2])ans[++cnt]=get(2);
            else{
                if(!size[4]||(size[4]&&hep[2][1]<hep[1][1]))ans[++cnt]=get(2);
                else ans[++cnt]=get(1),L=1-L;
            }
        }
        else{
            if(!size[3]&&!size[4])break;
            else if(!size[4]&&size[3])ans[++cnt]=get(3);
            else if(!size[3]&&size[4])ans[++cnt]=get(4),L=1-L;
            else{
                if(!size[1]||(size[1]&&hep[3][1]<hep[4][1]))ans[++cnt]=get(3);
                else ans[++cnt]=get(4),L=1-L;
            }
        }
    }
    if(L==R&&!size[1]&&!size[2]&&!size[3]&&!size[4]){
        ans[++cnt]=flg;
        for(int i=1;i<=cnt;i++)printf(i==cnt?"%d\n":"%d ",ans[i]);
    }
    else printf("-1\n");
    return 0; 
}