QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66059 | #5108. Prehistoric Programs | rumen_m# | WA | 10ms | 5856kb | C++14 | 3.1kb | 2022-12-06 03:20:11 | 2022-12-06 03:20:12 |
Judging History
answer
# include <bits/stdc++.h>
const long long MAXN = 1e6+5;
using namespace std;
struct ww
{
int id;
int ends;
int nms;
};
ww seq[MAXN];
bool cmp(ww i, ww j)
{
if(i.nms >= 0)
{
if( j.nms < 0) return true;
return i.ends >= j.ends;
}
if(j.nms >= 0) return false;
if(i.ends > 0)
{
if(j.ends <= 0) return true;
return i.ends <= j.ends;
}
if(j.ends > 0) return false;
return i.nms >= j.nms;
}
queue <int> ans;
vector <pair <int,int> > a,b,c;
bool got[MAXN];
priority_queue <pair <int,int> > pq;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
string s;
int i,j;
cin>>n;
int currD=0;
for(i = 1; i <= n; i++)
{
cin>>s;
seq[i].id= i;
seq[i].nms = 0;
seq[i].ends = 0;
for(char ch:s)
{
if(ch=='(')
{
seq[i].ends++;
}else
seq[i].ends--;
seq[i].nms = min(seq[i].nms,seq[i].ends);
}
if(seq[i].nms >= 0)
{
currD += seq[i].ends;
ans.push(i);
}else
if(seq[i].ends > 0)
a.push_back({-seq[i].nms,i});
else
{
b.push_back({seq[i].nms,i});
c.push_back({-seq[i].ends,i});
}
}
// sort(seq+1,seq+n+1,cmp);
sort(a.begin(),a.end());
for(i =0; i <a.size(); i++)
{
int curr= a[i].second;
if(currD < seq[curr].nms){cout<<"impossible\n";return 0;}
currD += seq[curr].ends;
ans.push(curr);
}
sort(b.begin(),b.end());
sort(c.begin(),c.end());
int uk1 = 0,uk2 = 0;
// cout<<currD<<endl;
while(uk1<b.size())
{
while(uk1<b.size() && got[b[uk1].second])uk1++;
while(uk2<c.size() && got[c[uk2].second]) uk2++;
if(uk1==b.size())break;
if(b[uk1].second!=c[uk2].second && (currD + seq[c[uk2].second].ends + seq[b[uk1].second].nms) >= 0)
{
// cout<<"Ok"<<endl;
currD += seq[c[uk2].second].ends;
ans.push(c[uk2].second);
got[c[uk2].second] = 1;
}else
{
// cout<<"OKK"<<endl;
if(currD+seq[b[uk1].second].nms < 0){cout<<(seq[b[uk1].second].nms+currD)<<"impossible\n";return 0;}
currD += seq[b[uk1].second].ends;
got[b[uk1].second]=1;
ans.push(b[uk1].second);
}
}
/*for(i = b.size()-1; i >=0; i--)
{
int curr = b[i].second;
if(currD < seq[curr].nms){cout<<"impossible\n";return 0;}
currD += seq[curr].ends;
ans.push(curr);
}*/
/* for(i =1; i <= n; i++)
{
cout<<seq[i].id<<endl;
if(currD + seq[i].nms < 0){cout<<"impossible\n";return 0;}
currD+=seq[i].ends;
}*/
if(currD!=0){cout<<"impossible\n";return 0;}
while(!ans.empty()){
cout<<ans.front()<<endl;
ans.pop();
}
}
/*
3
))))(((
)))
((((
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 10ms
memory: 5856kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
-11impossible
result:
wrong answer wrong output