QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66059#5108. Prehistoric Programsrumen_m#WA 10ms5856kbC++143.1kb2022-12-06 03:20:112022-12-06 03:20:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-06 03:20:12]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:5856kb
  • [2022-12-06 03:20:11]
  • 提交

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