QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391571#5108. Prehistoric ProgramssurenjamtsWA 3ms4068kbC++141.6kb2024-04-16 17:14:292024-04-16 17:14:31

Judging History

你现在查看的是最新测评结果

  • [2024-04-16 17:14:31]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4068kb
  • [2024-04-16 17:14:29]
  • 提交

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