题解：AT_arc190_a [ARC190A] Inside or Outside

胡金梁 · 2025-01-13 08:14:02 · 题解

赛时没有思路，但同机房的lbr巨佬一眼秒

首先，作为第一题，且赛时有人速通，再加上表意不明的题面，可知本题应为诈骗题。

可以手玩一下小样例或打表。然后可以发现一些性质：

1. 答案不会超过3（可证）
2. 答案为3的情况比较少

由此，我们可以大胆的分类讨论

考虑有解：

1. 答案为1，当且仅当存在一个区间，为[1,n]
2. 答案为2，可以是两个区间都执行2操作，当且仅当存在两个区间无公共点；可以是两个区间，分别执行1,2两个操作，当且仅当存在两个区间，满足其中一个区间能包含另一个区间，此时被包含的区间执行2操作，包含的区间执行1操作；可以是两个区间都执行1操作，当且仅当存在两个区间，相交且一个区间左端点为1，一个区间右端点为n。
3. 答案为三，当且仅当m>=3。

除去这三种情况，就可以直接输出-1了。

下面考虑答案为什么不会超过3

显然，除去答案为1,2的情况，一定满足这m个区间有至少一个公共点，且两两之间无包含与被包含关系，由此可以将这些区间以左端点为关键字排序，右端点也一定是有序的，这时直接取前三个区间[l_1,r_1],[l_2,r_2],[l_3,r_3](l_1<l_2<l_3,r_1<r_2<r_3)，可将1、3两个区间执行1操作，2区间执行2操作即可。

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
inline int read()
{
    int f=1,re=0;
    char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar();}
    while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^'0'),ch=getchar();
    return re*f;
}
struct node
{
    int l,r,id;
    bool operator <(const node &t) const
    {
        return (l==t.l?r>t.r:l<t.l);
    }
}q[200005];
signed main()
{
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].l=read(),q[i].r=read();q[i].id=i;
        if(q[i].l==1&&q[i].r==n)
        {
            cout<<1<<endl;
            for(int j=1;j<i;j++) cout<<0<<" ";
            cout<<1<<" ";
            for(int j=i+1;j<=m;j++) cout<<0<<" ";
            return 0; 
        }
    }
    sort(q+1,q+m+1);
    int rmax=q[1].r,rnum=q[1].id;
    for(int i=2;i<=m;i++)
    {
        if(q[i].r<=rmax)
        {
        //  cout<<q[i].l<<" "<<q[i].r<<" "<<rmax<<" "<<rnum<<endl;
            cout<<2<<endl;
            for(int j=1;j<min(rnum,q[i].id);j++)
            {
                cout<<0<<" ";
            }
            if(q[i].id<=rnum)
                cout<<2<<" ";
            else
                cout<<1<<" "; 
            for(int j=min(rnum,q[i].id)+1;j<max(q[i].id,rnum);j++)
            {
                cout<<0<<" ";
            }
            if(q[i].id<=rnum)
                cout<<1<<" ";
            else
                cout<<2<<" "; 
            for(int j=max(q[i].id,rnum)+1;j<=m;j++)
            {
                cout<<0<<" ";
            }
            return 0;
        }
        if(q[i].r>rmax) rmax=q[i].r,rnum=q[i].id;
    }
    int rmin=q[1].r;
    rnum=q[1].id;
    for(int i=2;i<=m;i++)
    {
        if(q[i].l>rmin)
        {
            cout<<2<<endl;
            for(int j=1;j<min(rnum,q[i].id);j++)
            {
                cout<<0<<" ";
            }
            cout<<2<<" ";
            for(int j=min(rnum,q[i].id)+1;j<max(q[i].id,rnum);j++)
            {
                cout<<0<<" ";
            }
            cout<<2<<" ";
            for(int j=max(q[i].id,rnum)+1;j<=m;j++)
            {
                cout<<0<<" ";
            }
            return 0;
        }
        if(q[i].r<rmin) rmin=q[i].r,rnum=q[i].id;
    }
    bool x1=0,x2=0;
    int i1,i2;
    for(int i=1;i<=m;i++)
    {
        if(q[i].l==1)
        {
            x1=1;
            i1=q[i].id;
        }
        if(q[i].r==n)
        {
            x2=1;
            i2=q[i].id;
        }
    }
    if(x1&&x2)
    {
        cout<<2<<endl; 
        for(int i=1;i<min(i1,i2);i++) cout<<"0 ";
        cout<<"1 ";
        for(int i=min(i1,i2)+1;i<max(i1,i2);i++) cout<<"0 ";
        cout<<"1 ";
        for(int i=max(i1,i2)+1;i<=m;i++) cout<<"0 ";
        return 0;
    }
    if(m>=3)
    {
        cout<<3<<endl;
        for(int i=1;i<min(min(q[1].id,q[2].id),q[3].id);i++) cout<<"0 ";
        if(q[1].id==min(min(q[1].id,q[2].id),q[3].id)||q[3].id==min(min(q[1].id,q[2].id),q[3].id)) cout<<"1 ";
        else cout<<"2 ";
        for(int i=min(min(q[1].id,q[2].id),q[3].id)+1;i<q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id);i++) cout<<"0 ";
        if(q[1].id==q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id)||q[3].id==q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id)) cout<<"1 ";
        else cout<<"2 ";
        for(int i=q[1].id+q[2].id+q[3].id-min(min(q[1].id,q[2].id),q[3].id)-max(max(q[1].id,q[2].id),q[3].id)+1;i<max(max(q[1].id,q[2].id),q[3].id);i++) cout<<"0 ";
        if(q[1].id==max(max(q[1].id,q[2].id),q[3].id)||q[3].id==max(max(q[1].id,q[2].id),q[3].id)) cout<<"1 ";
        else cout<<"2 ";
        for(int i=max(max(q[1].id,q[2].id),q[3].id)+1;i<=m;i++) cout<<"0 ";
        return 0;
    }
    cout<<-1<<endl;
    return 0;
}