#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
inline int read(){
	int XX=0,FF=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			FF*=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		XX=XX*10+ch-48;
		ch=getchar();
	}
	return XX*FF;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
int n,m;
bool ans[N];
string w[N],f[N];
string ch_max(string k){
	int head=1,tail=m,pos;
	if(head==tail)return k;
	char c=k[tail];
	while(head<=tail){
		if(k[tail]>c)c=k[tail],pos=tail;
		tail--;
	}
	k[pos]=k[head];
	k[head]=c;
	return k;
}
string ch_min(string k){
	int head=1,tail=m,pos;
	if(head==tail)return k;
	char c=k[tail];
	while(head<=tail){
		if(k[tail]<c)c=k[tail],pos=tail;
		tail--;
	}
	k[pos]=k[head];
	k[head]=c;
	return k;
}
bool compare(string x,string y){
	for(int i=1;i<=m;i++){
		if(x[i]==y[i])continue;
		else if(x[i]<y[i])return 1;
		else return 0;
	}
	return 0;
}
int main(){
//	cin.tie(0);
//	cout.tie(0);
	n=read();
	m=read();
	if(n==1){
		putchar('1');
		return 0;
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		w[i]=" "+w[i];
	}
	for(int i=1;i<=n;i++)
		f[i]=ch_max(w[i]);
	for(int i=1;i<=n;i++){
		string v=ch_min(w[i]);
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(!compare(v,f[j])){
				ans[i]=0;
				break;
			}
			else ans[i]=1;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i];
	return 0;
}

$O(n^2 m)的时间复杂度C++98开O2直接卡过了$

卡过

C++11&O2 40ptsRE*6