QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66052 | #5108. Prehistoric Programs | rumen_m# | WA | 79ms | 4140kb | C++14 | 2.5kb | 2022-12-06 02:45:21 | 2022-12-06 02:45:22 |
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;
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});
}
// sort(seq+1,seq+n+1,cmp);
sort(a.begin(),a.end());
for(i =0; i <a.size(); i++)
{
int curr= a[i].second;
cout<<curr<<endl;
while(!pq.empty() && currD < seq[curr].nms)
{
int x = pq.top().second;
pq.pop();
currD += seq[x].ends;
ans.push(x);
}
cout<<curr << " "<<seq[curr].nms<<" "<<currD<<endl;
if(currD < seq[curr].nms){cout<<"impossible\n";return 0;}
pq.push({seq[curr].ends,curr});
}
while(!pq.empty())
{
int x = pq.top().second;
pq.pop();
currD += seq[x].ends;
ans.push(x);
}
sort(b.begin(),b.end());
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: 79ms
memory: 4140kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
17 17 -1 27611 63 63 -1 27611 158 158 -1 27611 171 171 -1 27611 174 174 -1 27611 197 197 -1 27611 216 216 -1 27611 217 217 -1 27611 308 308 -1 27611 377 377 -1 27611 402 402 -1 27611 409 409 -1 27611 568 568 -1 27611 584 584 -1 27611 803 803 -1 27611 810 810 -1 27611 833 833 -1 2761...
result:
wrong answer your output is not a permutation of 1...n