QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66052#5108. Prehistoric Programsrumen_m#WA 79ms4140kbC++142.5kb2022-12-06 02:45:212022-12-06 02:45:22

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 02:45:22]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:4140kb
  • [2022-12-06 02:45:21]
  • 提交

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