QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66054#5108. Prehistoric Programsrumen_m#WA 97ms4136kbC++142.6kb2022-12-06 03:00:392022-12-06 03:00:41

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:00:41]
  • 评测
  • 测评结果:WA
  • 用时:97ms
  • 内存:4136kb
  • [2022-12-06 03:00:39]
  • 提交

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].ends-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: 100
Accepted
time: 97ms
memory: 4136kb

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

1
2
5
7
8
9
10
11
12
13
14
16
19
23
27
28
29
30
32
34
35
37
38
42
43
44
54
55
58
59
61
65
69
70
72
76
77
79
80
87
91
92
93
94
95
96
97
99
103
112
116
117
118
120
122
125
126
127
128
129
130
131
133
135
136
143
146
147
148
149
150
151
154
161
162
163
164
165
166
169
172
175
176
177
178
179
181
182
18...

result:

ok good plan

Test #2:

score: 0
Accepted
time: 9ms
memory: 3460kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

1
3
10
12
13
14
17
18
20
22
30
31
33
35
36
39
45
54
58
60
62
64
65
66
75
77
80
83
84
85
88
89
90
92
97
98
101
104
106
110
112
115
122
123
125
126
127
128
131
134
135
136
143
147
162
164
166
168
171
177
178
179
181
182
188
189
190
197
198
206
208
209
212
213
214
215
216
217
221
223
228
229
239
242
24...

result:

ok good plan

Test #3:

score: 0
Accepted
time: 2ms
memory: 3176kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0
Accepted
time: 2ms
memory: 3300kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 3336kb

input:

2
)(
()

output:

2
1

result:

wrong answer wrong plan (expected impossible)