P9446-ICPC-2021-WF-Prehistoric-Programs

先对其预处理，对每个字符串，用栈消掉能匹配的括号，剩下的必然是 )))...((( 的形式。记录左括号数 l、右括号数 r、权值 v = l - r，以及前缀和最小值 mp。

判定合法性，如果全局 sum(l) != sum(r)，直接 impossible。

那如何排序呢？

• 优先排 v >= 0（即 l >= r）的串。这类串对前缀和是正向贡献，按 r 从小到大排（消耗右括号越少的越安全）。

• 再排 v < 0 的串。这类串对前缀和是负向贡献，按 l 从大到小排（提供的左括号越多的越靠前）。

最后按排好的顺序累加前缀和，如果中途 sum + mp < 0，说明断链了，输出 impossible。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
	int v,l,r,mp,id;
}a[1000001];
signed main(){
	cin>>n;
	long long sl=0,sr=0;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		stack<char>st;
		for(int j=0;j<s.size();j++){
			if(s[j]=='(')st.push(s[j]);
			else{
				if(!st.empty()&&st.top()=='(')st.pop();
				else st.push(s[j]);
			}
		}
		int cur=0;
		while(!st.empty()){
			char c=st.top();
			st.pop();
			if(c=='(')a[i].l++;
			else a[i].r++;
		}
		for(int j=0;j<s.size();j++){
			if(s[j]=='(')cur++;
			else cur--;
			a[i].mp=min(a[i].mp,cur);
		}
		a[i].v=a[i].l-a[i].r,a[i].id=i;
		sl+=a[i].l,sr+=a[i].r;
	}
	if(sl!=sr){
		cout<<"impossible\n";
		return 0;
	}
	sort(a+1,a+n+1,[](const node&x,const node&y){
		bool xa=x.r<=x.l;
		bool ya=y.r<=y.l;
		if(xa!=ya)return xa;
		if(xa)return x.r<y.r;
		return x.l>y.l;
	});
	long long sum=0;
	for(int i=1;i<=n;i++){
		if(sum+a[i].mp<0){
			cout<<"impossible\n";
			return 0;
		}
		sum+=a[i].v;
	}
	if(sum!=0){
		cout<<"impossible\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		cout<<a[i].id<<endl;
	}
}