gym100801I Insider’s Information

题意

有一个排列满足 $m$ 条形如「 $y$ 出现在 $x,z$ 之间」的限制，现在你需要构造一个排列满足至少 $\lceil\frac{m}{2}\rceil$ 个限制。

题解

考虑从从两边往中间确定数(确定一个前缀和一个后缀)，也就是每次把一个数放到剩下区间的头或尾。

对于一个限制，如果第一个放的数是 $y$ 则一定满足不了条件。设第一个放的是 $x$，如果下一个放的是 $y$，则放在 $x$ 同侧就会满足限制。否则放在 $x$ 另一侧就会满足限制，也就是任何一个限制之和第一个数和第二个数的位置相关。

由于一定存在一个排列满足 $m$ 条限制，则一定能找到一个排列使得 $y$ 不同时在 $x,z$ 前面。每次放数的时候这个数作为「一个限制中第二个放的数」的所有限制一定要么要求放头要么要求放尾，选满足限制多的一边就可以了，容易证明一定满足 $\lceil\frac{m}{2}\rceil$ 条限制。

代码

/*
Author: QAQAutoMaton
Lang: C++
Code: I.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef complex<double> cp;
typedef pair<int,int> pii;
int inf;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T,class T2>int chkmin(T &a,T2 b){return a>b?a=b,1:0;}
template<class T,class T2>int chkmax(T &a,T2 b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T,class T2>T mmin(T a,T2 b){return a<b?a:b;}
template<class T,class T2>T mmax(T a,T2 b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
template<class T>bool sort2(T &a,T &b){return a>b?swap(a,b),1:0;}
#define min mmin
#define max mmax
#define abs aabs
struct __INIT__{
    __INIT__(){
        fill((unsigned char*)&inf,(unsigned char*)&inf+sizeof(inf),0x3f);
    }
}__INIT___;
namespace io {
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    // getchar
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    // print the remaining part
    inline void flush () {
        fwrite (obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }
    // putchar
    inline void putc (char x) {
        *oS ++ = x;
        if (oS == oT) flush ();
    }
    template<typename A>
    inline bool read (A &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
        return 1;
    }
    inline bool read (char &x) {
        while((x=gc())==' '||x=='\n' || x=='\r');
        return x!=EOF;
    }
    inline bool read(char *x){
        while((*x=gc())=='\n' || *x==' '||*x=='\r');
        if(*x==EOF)return 0;
        while(!(*x=='\n'||*x==' '||*x=='\r'||*x==EOF))*(++x)=gc();
        *x=0;
        return 1;
    }
    template<typename A,typename ...B>
    inline bool read(A &x,B &...y){
        return read(x)&&read(y...);
    }
    template<typename A>
    inline bool write (A x) {
        if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
        while (qr) putc (qu[qr --]);
        return 0;
    }
    inline bool write (char x) {
        putc(x);
        return 0;
    }
    inline bool write(const char *x){
        while(*x){putc(*x);++x;}
        return 0;
    }
    inline bool write(char *x){
        while(*x){putc(*x);++x;}
        return 0;
    }
    template<typename A,typename ...B>
    inline bool write(A x,B ...y){
        return write(x)||write(y...);
    }
    //no need to call flush at the end manually!
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[100005],b[100005],c[100005];
bitset<100005> vis;
vector<int> to[100005];
int ind[100005];
int dfn[100005],w[100005],t;
void dfs(int x){
    w[dfn[x]=++t]=x;
    --ind[x];
    for(auto i:to[x])if(!vis[i]){
        vis[i]=1;
        if(!--ind[b[i]])dfs(b[i]);
    }
}
int l,r;
int li[100005];
int p0[100005],p1[100005];
void pl(int x){li[++l]=x;}
void pr(int x){li[--r]=x;}
signed main(){
#ifdef QAQAutoMaton 
    freopen("I.in","r",stdin);
    freopen("I.out","w",stdout);
#endif
    int n,m;
    read(n,m);
    for(int i=1;i<=m;++i){
        read(a[i],b[i],c[i]);
        to[a[i]].emplace_back(i);
        to[c[i]].emplace_back(i);
        ++ind[b[i]];
    }
    for(int i=1;i<=n;++i)if(!ind[i])dfs(i);
    l=0,r=n+1;
    for(int i=1;i<=m;++i){
        if(dfn[a[i]]>dfn[c[i]])swap(a[i],c[i]);
        
    }
    for(int i=1;i<=n;++i){
        int x=w[i];
        if(p0[x]>p1[x]){
            pl(x);
            for(auto v:to[x])if(x==a[v]){
                if(dfn[b[v]]<dfn[c[v]]){++p0[b[v]];}    
                else ++p1[c[v]];
            }
        }
        else{
            pr(x);
            for(auto v:to[x])if(x==a[v]){
                if(dfn[b[v]]<dfn[c[v]]){++p1[b[v]];}    
                else ++p0[c[v]];
            }
        }
    }
    for(int i=1;i<=n;++i)write(li[i],i==n?'\n':' ');
    return 0;
}