QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66063#5108. Prehistoric Programsrumen_m#WA 136ms6204kbC++143.1kb2022-12-06 03:29:192022-12-06 03:29:21

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:29:21]
  • 评测
  • 测评结果:WA
  • 用时:136ms
  • 内存:6204kb
  • [2022-12-06 03:29:19]
  • 提交

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].ends,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: 100
Accepted
time: 136ms
memory: 6204kb

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: 1ms
memory: 3308kb

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: 0ms
memory: 3256kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0
Accepted
time: 3ms
memory: 5192kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5376kb

input:

2
)(
()

output:

2
1

result:

wrong answer wrong plan (expected impossible)