QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#391571 | #5108. Prehistoric Programs | surenjamts | WA | 3ms | 4068kb | C++14 | 1.6kb | 2024-04-16 17:14:29 | 2024-04-16 17:14:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(NULL);
int n;
cin>>n;
string s;
vector<pair<int,int>> begi;
vector<pair<pair<int,int>,int>> mid;
vector<pair<int,int>> en;
for(int i=0; i<n; i++){
cin>>s;
int cur=0;
string st="";
for(int j=0; j<s.size(); j++){
if(s[j]=='('){
cur++;
st+='(';
}
else{
if(st.size()>0 and st[st.size()-1]=='('){
st.pop_back();
}
else{
st+=')';
}
cur--;
}
}
// cout<<st<<endl;
cur=st.size();
if(cur==0) continue;
if(cur==1){
if(st[0]=='(') begi.push_back({cur,i});
else en.push_back({cur,i});
}
else{
int l=0, r=cur-1;
if(st[l]==st[r]){
if(st[l]=='(') begi.push_back({cur,i});
else{
en.push_back({cur,i});
}
}
else{
//mid
int mx=0;
for(int j=0; j<cur; j++){
if(st[j]==')') mx--;
else break;
}
//mx cur-mx cur-mx*2
mid.push_back({{mx,-cur+mx*2},i});
}
}
}
sort(mid.begin(),mid.end());
reverse(mid.begin(),mid.end());
vector<int> ans;
int cur=0;
for(int i=0; i<begi.size(); i++){
cur+=begi[i].first;
ans.push_back(begi[i].second);
}
for(int i=0; i<mid.size(); i++){
int fi=mid[i].first.first, se=-mid[i].first.second;
if(cur+fi<0){
cout<<"impossible"<<endl;
return 0;
}
cur+=se;
ans.push_back(mid[i].second);
}
for(int i=0; i<en.size(); i++){
cur-=en[i].first;
ans.push_back(en[i].second);
}
if(cur==0){
for(int i: ans){
cout<<i+1<<'\n';
}
}
else{
cout<<"impossible"<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 4068kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
impossible
result:
wrong answer you didn't find a solution but jury did