贪心练手题。
我们发现如果一对括号在一个串内能够匹配那我们直接就匹配完了，不会对其他的产生贡献。
先处理完所有能匹配的，这之后相当于我们把串变成了形如这样子的：
...))(((...
接着对于每个串我们可以得到两个值，一个是左边多出来的右括号的数量记作 \(a_i\)，另一个是右边多出来的左括号的数量记作 \(b_i\)。
然后根据一个括号匹配的经典技巧，左括号视作 \(1\)，右括号视作 \(-1\)，那么对于每一个前缀和我们都需要保证其不小于 \(0\)。且最后一个需要等于 \(0\)。
那么问题就变形成了选定一个对串的操作顺序，维护一个值 \(k\)。操作每个串时，先减去 \(a_i\) 再加上 \(b_i\)，期间每次操作完 \(k\) 均需保证其大于等于 \(0\)。那么如果能满足条件的顺序存在，其中必有一个顺序为尽可能使 \(k\) 每次操作完的最小值都尽可能大的顺序。
于是问题转化成了求 \(k\) 的最小值最大。
考虑一种感性的理解：
首先我们每次都先进行减法操作，那我之前操作完剩下的 \(k\) 值必然越大越优。
这时分两种情况，\(b_i > a_i\) 和 \(a_i > b_i\)，显然先选 \(b_i>a_i\) 可以得到更大的 \(k\) 以便后续操作。
接着考虑两个集合内部的顺序：
- \(b_i>a_i\) 时，由于先进行减法操作，所以我们应该选择 \(a_i\) 尽量小的元素先操作，这样子可以防止 \(k\) 不够大而减去过多。
- \(a_i>b_i\) 时，由于每个串操作完后 \(k\) 一定会变小，所以我们应该选择 \(b_i\) 尽量大的元素先操作，这样子可以让每次操作 \(k\) 尽可能得大来进行下一次减法操作。也可以从倒序的角度将这种情况转化成第一种来推。
这样子我们就可以通过一次排序来确定操作顺序。最后记录一下每次操作是否合法便可输出答案。
代码：
#include<bits/stdc++.h>
#define ll long long
#define e_b emplace_back
#define p_b push_back
#define gc getchar
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0)
const int N=1e6+5;
int rd(){int x=0,f=1;char c=gc();while(c>'9'||c<'0'){if(c=='-')f=-1;c=gc();}while(c<='9'&&c>='0')x=x*10+c-'0',c=gc();return x;
}
int n;
string s[N];
struct pii{int fir,sec,id;
}a[N];
bool cmp(pii x,pii y){if(x.fir>x.sec){if(y.fir>y.sec)return x.sec<y.sec;else return 1;}else{if(y.fir>y.sec)return 0;else return x.fir>y.fir;}
}
signed main(){ios;cin>>n;for(int i=1;i<=n;i++)cin>>s[i];for(int oo=1;oo<=n;oo++){string t=s[oo];int l=0,r=0;for(int i=0;i<t.size();i++){if(t[i]=='(')l++;else{if(l)l--;else r++;}}a[oo]={l,r,oo};}sort(a+1,a+n+1,cmp);int k=0;for(int i=1;i<=n;i++){k-=a[i].sec;if(k<0)cout<<"impossible",exit(0);k+=a[i].fir;}if(!k)for(int i=1;i<=n;i++)cout<<a[i].id<<'\n';else cout<<"impossible";}