T1神奇做法AC（求正确性证明/hack）

//ti mu kan cuo le aaaaaaaaa

#include <bits/stdc++.h>
using namespace std;
#define N 3050
int n,len;
string st[N];
int minn[N];//now min max zidianxu
int a[N];//new string
int gz[N];//gou zao new string
int rp[N];
int tsort[30];
int compmin[30],noww[30];
bool cmp(int a,int b)
{
    return a>b;
}
bool pduniq()//true xiangtong
{
    for(int i=1;i<=len;i++)
        if(gz[i]!=minn[i]) return false;
    return true;
}
bool pduniq2()//true xiangtong
{
    for(int i=1;i<=26;i++)
        if(compmin[i]!=noww[i]) return false;
    return true;
}
char xwx[N][N];
bool cm(int i,int j)
{
    for(int k=0;k<len;k++)
        if(xwx[i][k]<xwx[j][len-k-1]) return true;
        else if(xwx[i][k]>xwx[j][len-k-1]) return false;
    return true;
}
void work()
{
    for(int ii=1;ii<=n;ii++)
    {
        cin>>xwx[ii];
        sort(xwx[ii],xwx[ii]+len);
    }
    for(int i=1;i<=n;i++)
    {
        int pd=1;
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(cm(i,j)==0)
            {
                pd=0;
                break;
            }
        }
        cout<<pd;
    }
}
int main()
{
//    freopen("dict.in","r",stdin);
//    freopen("dict.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>len;
    if(n==1)
    {
        cout<<1;
        return 0;
    }
    if(len>=2&&len<=300)
    {
        work();
        return 0;
    }
    for(int ii=1;ii<=n;ii++)
    {

      //  for(int i=1;i<=len;i++)
     //      cout<<char(minn[i]+'a'-1)<<' ';
    ///   cout<<endl;

        cin>>st[ii];
        for(int i=1;i<=len;i++)
            a[i]=st[ii][i-1]-'a'+1;

        //clear
        for(int i=0;i<30;i++)
            tsort[i]=0;

        //tong sort
        for(int i=1;i<=len;i++)
            tsort[a[i]]++;

        if(ii==1)
        {
            int minnlen=0;
            for(int i=26;i>0;i--)
                for(int j=1;j<=tsort[i];j++)
                    minn[++minnlen]=i;
        //    cout<<1;
            continue;
        }
/*
        sort(a,a+len+1);
        //pd last
        if(a[len]<minn[1])
        {
            cout<<1;
            for(int i=len;i>0;i--)
                minn[i]=a[len-i+1];
            continue;
        }*/

        int nlen=0;//new string's length
        int pd=0;
        while(nlen<len)
        {
        //    cout<<minn[nlen+1]-1<<endl;
            //if ==
            if(tsort[minn[nlen+1]]>0)
            {
                nlen++;
                gz[nlen]=minn[nlen];
                tsort[minn[nlen]]--;
                continue;
            }
            //if <
            for(int i=minn[nlen+1]-1;i>0;i--)
            {
            //    cout<<i<<" "<<tsort[i]<<endl;
                if(tsort[i]>0)
                {
                    gz[++nlen]=i;
                    tsort[i]--;

                    for(int j=26;j>0;j--)
                        while(tsort[j]>0) gz[++nlen]=j,tsort[j]--;
                 //   cout<<1;
                    pd=1;
                    break;
                }
            }
            if(pd==1) break;
            if(pd==0)
            {
            //    cout<<0;
                break;
            }
        }
        //if the minn==gz(yang li)
        if(pduniq()==true)
        {
        //    cout<<1;
            for(int i=1;i<len;i++)
                if(minn[i]!=minn[i+1])
                {
                    swap(minn[i],minn[i+1]);
                    break;
                }
            continue;
        }
        if(pd==0) continue;
        swap(minn,gz);

    }
//    sort(minn+1,minn+1+len,cmp);
//    for(int i=1;i<=len;i++)
//        cout<<char(minn[i]+'a'-1)<<' ';
    for(int i=1;i<=len;i++)
            compmin[minn[i]]++;
    for(int ii=1;ii<=n;ii++)
    {
        for(int i=0;i<30;i++)
            noww[i]=0;
        for(int i=1;i<=len;i++)
            rp[i]=0;
        int rplen=0;
        for(int i=1;i<=len;i++)
            noww[st[ii][i-1]-'a'+1]++;

        for(int i=1;i<=26;i++)
            for(int j=1;j<=noww[i];j++)
                rp[++rplen]=i;

        if(pduniq2()) cout<<1;
        else
        {
            int pd=0;
            for(int i=1;i<=len;i++)
                if(rp[i]<minn[i])
                {
                    pd=1;
                    break;
                }
            cout<<pd;
        }
    }


    return 0;
}