QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#110375	#5108. Prehistoric Programs	jyhptr	TL	260ms	10212kb	C++20	2.7kb	2023-06-01 18:27:36	2023-06-01 18:27:38

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-01 18:27:38]
评测

测评结果：TL
用时：260ms
内存：10212kb

查看

[2023-06-01 18:27:36]
提交

answer

// compile: make data
// run: time ./data < data.in > data.out
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#else
#define debug(x...) {};
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define double long double
#define int long long
#define MAXN 1000010
#define MAXM 12000000

struct node {
    int minv, sum, id;
};
node pos[MAXN], neg[MAXN];
char ch[MAXM];

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    // int n; cin >> n;

    // int lenn = 0, lenp = 0;
    // rep(i, 0, n) {
    //     // string ch; cin >> ch;
    //     scanf("%s", ch);
    //     int minv = 0, sum = 0;
    //     int len = strlen(ch);
    //     rep(j, 0, len) {
    //         if (ch[j] == '(') sum++;
    //         else sum--;
    //         minv = min(minv, sum);
    //     }
    //     // if (sum >= 0) pos.push_back({minv, sum, i+1});
    //     // else neg.push_back({minv, sum, i+1});
    //     if (sum >= 0) pos[lenp++] = {minv, sum, i+1};
    //     else neg[lenn++] = {minv, sum, i+1};
    // }

    int n = 0, p = 0;
    fread(ch, 1, MAXM, stdin);
    while (ch[p] != '\n') n = n * 10 + ch[p++] - '0';
    while (ch[p] == '\n') ++p;
    int minv = 0, sum = 0;
    int lenp = 0, lenn = 0;
    for (int i = 0; i < n; ++p) {
        if (ch[p] == '\n') {
            if (sum >= 0) pos[lenp++] = {minv, sum, i + 1};
            else neg[lenn++] = {minv, sum, i + 1};
            ++i;
            minv = sum = 0;
            continue;
        }
        sum += (ch[p] == '(' ? 1 : -1);
        minv = min(minv, sum);
    }


    sort(pos, pos + lenp, [](node a, node b) {
        return a.minv > b.minv;
    });
    sort(neg, neg + lenn, [](node a, node b) {
        return a.minv <= b.minv;
    });
    sum = 0;
    rep(i, 0, lenp) {
        if (sum + pos[i].minv < 0) {
            cout << "impossible" << endl;
            return 0;
        }
        sum += pos[i].sum;
    }
    rep(i, 0, lenn) {
        if (sum + neg[i].minv < 0) {
            cout << "impossible" << endl;
            return 0;
        }
        sum += neg[i].sum;
    }
    if (sum != 0) {
        cout << "impossible" << endl;
        return 0;
    }
    rep(i, 0, lenp) printf("%lld\n", pos[i].id);
    rep(i, 0, lenn) printf("%lld\n", neg[i].id);

    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 260ms

memory: 10212kb

input:

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

output:

result:

ok good plan

Test #2:

score: 0

Accepted

time: 3ms

memory: 9832kb

input:

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

output:

result:

ok good plan

Test #3:

score: 0

Accepted

time: 2ms

memory: 5528kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0

Accepted

time: 3ms

memory: 7812kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: 0

Accepted

time: 2ms

memory: 5380kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0

Accepted

time: 0ms

memory: 7592kb

input:

3
()
(
)

output:

1
2
3

result:

ok good plan

Test #7:

score: 0

Accepted

time: 3ms

memory: 7664kb

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

score: 0

Accepted

time: 0ms

memory: 7816kb

input:

5
))(
(()
)(
(
)

output:

result:

ok good plan

Test #9:

score: 0

Accepted

time: 2ms

memory: 7724kb

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

score: 0

Accepted

time: 0ms

memory: 7472kb

input:

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

output:

impossible

result:

ok impossible

Test #11:

score: 0

Accepted

time: 2ms

memory: 7616kb

input:

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

output:

result:

ok good plan

Test #12:

score: 0

Accepted

time: 1ms

memory: 7776kb

input:

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

output:

result:

ok good plan

Test #13:

score: 0

Accepted

time: 1ms

memory: 7736kb

input:

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

output:

result:

ok good plan

Test #14:

score: 0

Accepted

time: 2ms

memory: 7784kb

input:

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

output:

result:

ok good plan

Test #15:

score: 0

Accepted

time: 3ms

memory: 7780kb

input:

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

output:

result:

ok good plan

Test #16:

score: 0

Accepted

time: 3ms

memory: 7856kb

input:

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

output:

result:

ok good plan

Test #17:

score: 0

Accepted

time: 3ms

memory: 7676kb

input:

750
(()()((()((((())()((()))()()))()))(()()(()))(()(())()))((((((
)))))))
)
((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()(
)
)
(
)()(((()(())))()))))(((((((()))()()()(()())))(()())(()((
(
)
)(()))
((())(...

output:

result:

ok good plan

Test #18:

score: 0

Accepted

time: 0ms

memory: 7624kb

input:

100
)
)
)
(
)
(
))))()
)
(
(
(
(
)
)
)
)
(
(
(
(
())
(
)
)
)((
)
(
(
(
)
(
(
)
)
)
)
()((
(
)
)
)
)(((
((((
(
)
(
)
((
)
(
(
)
(
())(()))
)
)
(
)
(
(
(
(
)))()()
)
(
(
(
(
)
(
)
)
)
(
)
)
)
)
(
)
(
(
)
(
)
(
(
(
)
)
(
)
)
(
)((((
)
)
()((()()(()))))
)
(

output:

result:

ok good plan

Test #19:

score: 0

Accepted

time: 3ms

memory: 7464kb

input:

100
)
()(
(
)
(
)
(
(
)
)
)(()
)
)))
)
)
(
(
(
)
(
(
)
(
)
(
(
(
))(
(
(
))((
(
)
(
))())
)
(()
)
)
(
)
(
(
)
)
(
)
(
))
(
(
)
)
(
)
)
)
)
(
())
)
(
(
)
)
(
)
(
))
(
)
)
(
(
(((
(
(
(()
)
)()())(()((()((())
(
)
)
(
(
)
)
(
)
(
)
(
))(
)
(
(
(
)
(
(((())

output:

impossible

result:

ok impossible

Test #20:

score: 0

Accepted

time: 2ms

memory: 7624kb

input:

100
)
)
()))((((
))()
(
(
(
)
(
)
(
(
)
()
(
(
)
)
(
)
(
(
)
)
)
(
)
)
(
(
)
)
(
)
)
)
)
(
(
)
((
(
(
)
)
(
(
)
(
)
(()((
)
(
)
)
(()))()()())))()()((
(
)
)
(
(
(
)
)
(
(
)
(
(
(
)
(
(
)
)(
(
)
)
)
(
(())())(()
)
)
(
()
((
(
)
)
)
)
(
)
(
(
)
)
(
())
)(

output:

result:

ok good plan

Test #21:

score: 0

Accepted

time: 1ms

memory: 7848kb

input:

100
(
(
)
(
)
(
(
(
(
)
)
)
)
()
)(
)
)
(
(
)
(
(
)
)
)
(
)
(
(
))))
(
)
(
)
(
(
(
()()(
)
())
(
(
)
)
(
(
)
(
(
)
)
(
(
(
(
(
)
(
(
(((
)
)
)
))))
(
))(
)
)
()
())()
)
)
(
)))
(
)((()))(
(
(((
((
(
)
(
(
)
(
)
)
()
)()
)
)
()))()(
)(())(
)
(
(
(
(
)(
)

output:

result:

ok good plan

Test #22:

score: 0

Accepted

time: 3ms

memory: 7484kb

input:

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

output:

impossible

result:

ok impossible

Test #23:

score: 0

Accepted

time: 4ms

memory: 7552kb

input:

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

output:

impossible

result:

ok impossible

Test #24:

score: 0

Accepted

time: 2ms

memory: 7552kb

input:

4000
(
)
))
)()))))(
(
)
(
)
)
)
)((()((
(
)
)()(
)
)
)
)
(
)
(
)
)
(
()))((()))))()((()(
(
)))
(
)
(
(
(
(
)
)()(()()(()()))))())
)
)
)(((
)
)
)
)
(
(
)
))()()))((())
(
(
)
(
))(
(
)
)
(
)
)
())(
)
(
(
(
)
())))(())((()(()()((()((
(
)
)
(
)
)
)
)
)
)
)
)
(
)
(()))))(
)
)
(
())))(((())()(
(
(
()(
(
...

output:

impossible

result:

ok impossible

Test #25:

score: -100

Time Limit Exceeded

input:

1000000
)
(
)()(((()))(
(
(
(
)
(
(
)
)
(((())((()(()((())
(
)
)(
)
)
))))(()))()())(()((()))(()()()))()()()))))))))(())))((((()(()()))((((((()((((()()(
)
((
)
)
(
)
())()()((
)
)))(())((()))((()()))(()(())())))())))())))(()()(
(
()(
(
(
()()
)
))
)
(
(
(
)
)
)
(
)
(
)
)
)
)(()))()))
(
)
)))
(
)
(
(...