题解：AT_arc205_c [ARC205C] No Collision Moves

· · 题解

赛时场切了，现在发现忘记补题解于是再做一遍谔谔。

显然按照题意操作后每个人的相对位置不会改变。

因此按左端点排序比较右端点即可检验局面是否合法。

我们用 \text{op}_i 表示第 i 个人的运行方向：

排序后，我们从左到右处理时，显然的所有的 \texttt{0} 段都可以直接运行，而 \texttt1 段则需要从后往前倒着做。

倒着做的部分用栈即可。

时间复杂度 O(n\log n)，瓶颈在于排序。

#include<bits/stdc++.h>
#define mk make_pair
#define pb push_back
#define mod 998244353
#define int long long
using namespace std;
int read(){
    int sum=0,fish=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')fish=-1,c=getchar();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=getchar();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
struct fish{
    int l,r,id;
    bool op;
}a[200005];
bool cmp(fish x,fish y){
    return x.l<y.l;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].id=i;
        a[i].op=a[i].l<a[i].r;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<n;i++)
    if(a[i].r>a[i+1].r){
        puts("No");
        return;
    }
    puts("Yes");
    stack<int>s;
    for(int i=1;i<=n;i++){
        if(a[i].op)s.push(a[i].id);
        else{
            while(!s.empty())cout<<s.top()<<' ',s.pop();
            cout<<a[i].id<<' ';
        }
    }
    while(!s.empty())cout<<s.top()<<' ',s.pop();
}
signed main(){
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
// 科里拿第尔契市现在也立著许多她的石像，或是将她当成绘画主题。
// 描写一连串事件真相的歌剧变成剧场的固定节目，纪念博物馆打出「连那位英雄也赞不绝口」的口号贩卖的叶菜羊肉卷（Wrapped Lamb）也十分畅销。

// 这些粉饰过的故事其实原本都只是些芝麻小事。
// 外加因为每尊石像都被美化过，所以即使本人站在石像前面也不会被认出来（这让潘丽宝大笑了一番）；
// 歌剧的剧情当然也几乎都是虚构（演费奥多尔的演员是个超帅气的白色虎头兽人）；
// 叶菜羊肉卷则是真的很好吃（但当初赞不绝口的人是可蓉）。