QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379854#5108. Prehistoric Programscciafrino#WA 8ms3788kbC++201.7kb2024-04-06 19:32:432024-04-06 19:32:43

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 19:32:43]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3788kb
  • [2024-04-06 19:32:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N; cin >> N;

    int total_balance = 0;
    vector<int> good, bad;
    vector<pair<int, int>> v(N);
    for (int i =0; i < N; ++i) {
        string S; cin >> S;
        int minus = 0, plus = 0;
        int balance = 0, min_balance = 1e9;
        for (auto c : S) {
            if (c == ')') {
                minus++;
                balance -= 1;
            }
            else {
                plus++;
                balance += 1;
            }
            min_balance = min(min_balance, balance);
        }

        v[i] = {min_balance, balance};
        total_balance += balance;
        if (balance < 0) {
            bad.push_back(i);
        } else {
            good.push_back(i);
        }
    }

    if (total_balance != 0) {
        cout << "impossible\n";
    } else {
        sort(good.begin(), good.end(), [&](const auto& l, const auto& r) {
            return v[l].first > v[r].first;
        });
        sort(bad.begin(), bad.end(), [&](const auto& l, const auto& r) {
            return v[l].first - v[l].second < v[r].first - v[r].second;
        });

        int sum = 0;
        bool works = true;
        for (auto id : good) {
            works |= (sum + v[id].first < 0);
            sum += v[id].second;
        }
        for (auto id : bad) {
            works |= (sum + v[id].first < 0);
            sum += v[id].second;
        }

        if (works) {
            for (int id : good) cout << id+1 << '\n';
            for (int id : bad) cout << id+1 << '\n';
        } else {
            cout << "impossible\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 3788kb

input:

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

output:

30754
30788
30786
30781
30779
30778
30775
30771
30766
30765
30764
30790
30750
30748
30747
30746
30745
30743
30741
30737
30736
30735
30810
30860
30859
30857
30856
30855
30850
30847
30845
30834
30813
30734
30809
30804
30803
30799
30798
30797
30796
30793
30792
30791
30660
30680
30677
30672
30671
30669
...

result:

ok good plan

Test #2:

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

input:

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

output:

655
685
287
681
680
291
673
668
667
666
663
301
662
309
659
316
282
324
652
327
329
650
646
334
335
640
636
632
628
347
615
611
252
216
217
752
748
223
228
229
747
746
738
242
243
732
245
247
604
253
257
258
725
719
715
711
265
267
268
707
271
689
687
280
516
422
557
426
554
553
430
544
535
534
439
...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3524kb

input:

2
)(
()

output:

2
1

result:

wrong answer wrong plan (expected impossible)