QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66031#5108. Prehistoric Programsbili2002#WA 17ms4280kbC++173.9kb2022-12-06 00:48:142022-12-06 00:48:17

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 00:48:17]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:4280kb
  • [2022-12-06 00:48:14]
  • 提交

answer


#include <bits/stdc++.h>
#define f first
#define s second
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back

using namespace std;
using ll = long long;

template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is,       pair<T, T2> &p)             { is>>p.f>>p.s;        return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p)             { os<<p.f<<' '<<p.s;   return os; }
template<class T>           inline istream &operator>>(istream &is,       vector<T> &v)               { for (auto &id : v)   is>>id;       return is; }
template<class T>           inline ostream &operator<<(ostream &os, const vector<T> &v)               { for (auto id : v)    os<<id<<'\n';  return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m)              { for (auto id : m)    os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um)   { for (auto id : um)   os<<id<<'\n'; return os; }
template<class T>           inline ostream &operator<<(ostream &os, const list<T> &l)                 { for (auto id : l)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const set<T> &s)                  { for (auto id : s)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const unordered_set<T> &us)       { for (auto id : us)   os<<id<<' ';  return os; }
const long long INF = 1e18;
const bool hasTests = 0;

struct par {
    int op, cl;
    int id;
    bool neg;
    int highestMin;

    bool operator<(const par& oth) {
        if (!neg && oth.neg) {
            return true;
        }
        if (neg && !oth.neg) {
            return false;
        }

        if (op - cl > 0 && oth.op - oth.cl < 0) {
            return true;
        }
        if (op - cl < 0 && oth.op - oth.cl > 0) {
            return false;
        }

        if (op - cl < 0) {
            return highestMin < oth.highestMin;
        } else {
            return highestMin > oth.highestMin;
        }
    }
};

vector<par> p;

bool pos;
vector<int> ans;
int n;

void input() {
    cin>>n;
    p.resize(n);

    string s;
    for (int i=0; i<n; i++) {
        cin>>s;
        p[i].id = i;
        p[i].neg = false;
        for (auto curr : s) {
            if (curr == '(') {
                p[i].op++;
            } else {
                p[i].cl++;
            }
            if (p[i].op < p[i].cl) {
                p[i].neg = true;
            }
            p[i].highestMin = min(p[i].highestMin, p[i].op - p[i].cl);
        }
        //cerr<<i<<' '<<p[i].highestMin<<' '<<p[i].neg<<endl;
    }
}

void output() {
    if (!pos) {
        cout<<"impossible"<<endl;
        return;
    }

    cout<<ans<<endl;
}

void solve() {
    sort(all(p));

    pos = true;
    int cntOp = 0, cntCl = 0;
    for (auto& curr : p) {
        //cout<<curr.id<<' '<<cntOp + curr.highestMin<<' '<<cntCl<<endl;
        if (cntOp + curr.highestMin < cntCl) {
            pos = false;
            break;
        }

        cntOp += curr.op;
        cntCl += curr.cl;
        ans.pb(curr.id + 1);
    }

    if (cntOp != cntCl) {
        pos = false;
    }

}

void start() {
    int t = 1;
    if (hasTests) {
        cin>>t;
    }

    for (int i=1; i<=t; i++) {
        input();
        solve();
        //cout<<"Case #"<<i<<": ";
        output();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    start();
    return 0;
}

/*
7
((((()
()))))
(
)
((
))((
))

3
(((((
)))))((((
))))

2
()
*/


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 17ms
memory: 4280kb

input:

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

output:

26700
26740
26738
26737
26729
26727
26724
26723
26716
26715
26714
26713
26711
26709
26703
26744
26698
26696
26695
26693
26692
26689
26685
26682
26679
26677
26674
26672
26671
26670
26779
26819
26817
26815
26813
26810
26809
26806
26803
26802
26800
26792
26787
26784
26783
26668
26778
26777
26776
26773
...

result:

ok good plan

Test #2:

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

input:

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

output:

245
498
258
257
502
253
252
863
668
247
511
725
243
242
514
731
239
732
943
667
516
517
934
287
286
481
719
282
280
869
489
933
673
945
935
819
271
820
268
267
496
265
799
189
822
534
198
197
535
854
663
746
544
190
948
188
747
662
182
181
852
179
178
177
748
217
798
859
229
228
522
524
738
223
666
...

result:

ok good plan

Test #3:

score: 0
Accepted
time: 1ms
memory: 3252kb

input:

2
()
()

output:

1
2


result:

ok good plan

Test #4:

score: 0
Accepted
time: 1ms
memory: 3252kb

input:

2
((
))

output:

1
2


result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

1
2
3


result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3


result:

ok good plan

Test #8:

score: 0
Accepted
time: 0ms
memory: 3252kb

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5


result:

ok good plan

Test #9:

score: 0
Accepted
time: 0ms
memory: 3372kb

input:

3
((
))())
(

output:

1
3
2


result:

ok good plan

Test #10:

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

input:

6
)
()
()()()
((
)
)

output:

impossible

result:

ok impossible

Test #11:

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

input:

500
(
)
)
(
)(
(
(
)
))(
(
(
(
(
)
)
(
(
)
(
(
)
(
()(()
(
)())
(
(
)
(
)()((
(
)
(
)
)
(
(
(
)
(
(
)
)
)(
(
(
)
)
(
)
(
(
(
)
(
(
())))
(
(
(
)
(
)
)
(
(
)
)
(
(
(
(
(
()
(
(
(
(
(
((
)
(
(
)
(
(
(
)
())
(
(
(
)
(
(
(
)
)
(
)
)
(
)
(
(
(
(
)
(
)
)
)
)
(
)
)))()(
(
)
)
(
)
)(
)
(
)
)
))
(
(
(
(
(
(
...

output:

204
414
211
210
209
208
207
415
205
413
203
416
199
198
196
420
194
192
404
398
234
399
232
401
228
227
226
191
405
406
219
409
410
411
412
214
157
435
436
437
438
439
160
159
158
166
156
440
153
152
442
443
149
445
178
424
186
184
426
182
427
180
428
395
177
176
429
172
171
431
434
308
321
320
318
...

result:

ok good plan

Test #12:

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

input:

50
)
)
((((()())())))(())(())
()(((()))
(((()))(()
()(((
))
)
)()))(()(()())(((((()
(
)
)
)((
)()((
())()))
(())))()
(((
))))(()
()(())(()))())()
)
)
(
(
(
(
((())()())())))(((())
()(
(()(())()((()
()(((()())))())()(
)
)((()
(
)
((
)
()(
(
(
)
)))((())
)
()))()(((()(()
((
((()))(())(()())(()())())()...

output:

17
32
34
28
27
36
25
24
23
22
37
38
43
3
4
5
10
6
13
31
29
14
46
42
9
45
44
50
49
18
40
26
15
7
48
47
19
16
2
33
8
11
12
41
39
20
21
1
35
30


result:

ok good plan

Test #13:

score: 0
Accepted
time: 1ms
memory: 3216kb

input:

50
)
(
)()(
())(
()()(((((())(
)(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...

output:

2
47
46
41
40
33
28
26
18
16
15
13
11
5
8
37
29
21
6
31
36
12
17
23
39
43
38
4
42
32
44
45
3
1
48
49
50
35
34
30
7
27
25
24
22
20
19
9
10
14


result:

ok good plan

Test #14:

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

input:

150
))(()))(())(())))()))())()()()(())(((())))()))))()
)))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...

output:

49
28
140
32
136
35
37
38
40
92
130
73
94
48
84
120
52
53
69
111
106
105
60
104
103
100
98
20
12
148
14
15
11
17
87
79
149
143
142
7
6
24
141
4
16
61
96
10
117
62
5
51
70
93
129
133
91
23
135
89
137
27
29
102
77
147
2
122
125
25
9
3
56
115
47
43
41
18
86
134
150
59
45
85
30
19
72
21
71
127
50
81
116...

result:

ok good plan

Test #15:

score: -100
Wrong Answer
time: 3ms
memory: 3248kb

input:

150
)))(
(()
(())((())))(()))()(()
((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()())))))
(
...

output:

impossible

result:

wrong answer you didn't find a solution but jury did