QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373758#5108. Prehistoric ProgramsAnish_aakRE 12ms6536kbC++142.7kb2024-04-02 04:19:202024-04-02 04:19:21

Judging History

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

  • [2024-04-02 04:19:21]
  • 评测
  • 测评结果:RE
  • 用时:12ms
  • 内存:6536kb
  • [2024-04-02 04:19:20]
  • 提交

answer

#include <bits/stdc++.h>
// #pragma comment(linker, "/STACK:268435456");,
using namespace std;

#define int             long long
#define double          long double
#define pb              push_back
#define all(t)          (t).begin(), (t).end()
#define rep(i,j)        for(int i = 0; i < (j); ++i)
#define rrep(i,j)       for(int i = (j)-1; i >= 0; --i)
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
const char nl = '\n';
const double eps = 1e-6;
const int N = 1e5, mod = 1e9 + 7, inf = 1e18;

void solve()
{
    int n; cin >> n;
    vector<string> s(n);
    for(auto &i: s) cin >> i;
    vector<pair<pair<int, int>, int>> l, r;
    rep(i, n) {
        int cur = 0, mn = 0;
        for(auto c: s[i]) {
            cur += (c == '(') - (c == ')');
            mn = min(mn, cur);
        }
        reverse(all(s[i]));
        // if(cur >=0)
        // cout << mn << " l " << cur << nl;
        if(cur < 0) {
            cur = 0; mn = 0;
            for(auto c: s[i]) {
                cur += (c == ')') - (c == '(');
                mn = min(mn, cur);
            }
            r.pb({{abs(mn), cur}, i});
        // cout << mn << ' ' << cur << nl;

        }
        else l.pb({{abs(mn), cur}, i});
    }
    sort(all(l));
    sort(all(r));
    if(l[0].first.first != 0 || r[0].first.first != 0) {
        cout << "impossible\n"; return;
    }
    int cur1 = 0, cur2 = 0;
    rep(i, (int)l.size() - 1) {
        cur1 += (l[i].first.second - l[i+1].first.first);
        if(cur1 < 0) {
            cout << "impossible\n"; return;
        }
        cur1 += l[i+1].first.first;
    }
    // cout << cur1 << ' ';
    cur1 += l.back().first.second;
    rep(i, (int)r.size() - 1) {
        cur2 += (r[i].first.second - r[i+1].first.first);
        if(cur2 < 0) {
            cout << "impossible\n"; return;
        }
        cur2 += r[i+1].first.first;
    }
    cur2 += r.back().first.second;
    // cout << cur1 << ' ' << cur2 << nl;
    if(cur1 != cur2) {
        cout << "impossible\n"; return;
    }
    for(auto i: l) cout << i.second + 1 << nl;
    reverse(all(r));
    for(auto i: r) cout << i.second + 1 << nl;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(numeric_limits<double>::max_digits10);
    cout << setprecision(15) << fixed;
    #ifdef aak_local
       freopen("/Users/aak/Desktop/Comding/Competitive/input.txt","r",stdin);
       freopen("/Users/aak/Desktop/Comding/Competitive/output.txt","w",stdout);
    #endif
    int tt = 1;
    // cin >> tt;
    for(int i = 1; i <= tt; ++i)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 6536kb

input:

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

output:

13
29
65
69
103
129
133
163
164
172
178
241
307
383
418
506
540
542
586
608
652
687
826
896
919
925
929
969
1021
1031
1060
1093
1141
1170
1334
1491
1677
1689
1753
1767
1911
1946
1978
2004
2087
2135
2170
2216
2238
2321
2380
2420
2472
2540
2551
2560
2665
2724
2735
2743
2768
2812
2892
2933
2937
3064
30...

result:

ok good plan

Test #2:

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

input:

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

output:

30
35
45
84
85
112
115
123
128
197
221
297
397
429
433
489
596
617
626
653
762
788
790
879
962
983
1
3
10
12
14
18
22
54
58
64
65
75
77
89
90
92
97
101
104
106
110
122
125
126
135
136
143
147
162
166
178
179
181
182
188
189
190
198
206
209
212
213
215
216
217
223
228
229
242
243
245
247
252
253
265
...

result:

ok good plan

Test #3:

score: -100
Runtime Error

input:

2
()
()

output:


result: