QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66050#5108. Prehistoric Programsrumen_m#WA 1087ms5676kbC++141.3kb2022-12-06 02:26:422022-12-06 02:26:45

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:26:45]
  • 评测
  • 测评结果:WA
  • 用时:1087ms
  • 内存:5676kb
  • [2022-12-06 02:26:42]
  • 提交

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;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    string s;
    int i,j;
    cin>>n;
    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);
        }
    }
    sort(seq+1,seq+n+1,cmp);
    int currD=0;

    for(i  =1; i <= n; i++)
    {
       if(currD - seq[i].nms < 0){cout<<"impossible\n";return 0;}
       currD+=seq[i].ends;
    }
    if(currD!=0){cout<<"impossible\n";return 0;}
    for(i = 1; i <=n; i++)
        cout<<seq[i].id<<endl;

        }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1087ms
memory: 5676kb

input:

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

output:

41248
4238
13809
5338
27609
48374
389
2458
48749
6754
42979
18533
14096
6986
31692
32583
5803
23456
3405
169
10427
26695
43508
26677
38930
9225
34539
2253
46429
11398
41740
25061
24373
35132
39743
30771
46194
21764
5699
31402
33777
45491
35039
34110
23312
35743
41641
41639
463
7365
9790
6701
23551
3...

result:

ok good plan

Test #2:

score: 0
Accepted
time: 11ms
memory: 3452kb

input:

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

output:

36
13
66
386
966
585
286
257
83
127
39
476
595
329
907
814
214
598
62
427
981
707
662
384
131
511
807
793
638
869
449
80
271
767
379
422
746
387
327
239
474
632
20
553
171
915
919
334
535
345
296
989
168
975
31
715
473
502
88
390
947
98
17
725
464
177
686
164
604
945
316
827
881
852
819
406
134
258
...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

2
1

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

2
1

result:

wrong answer wrong plan (expected impossible)