QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521476#5108. Prehistoric ProgramsAndycipationWA 6ms3860kbC++201.1kb2024-08-16 11:16:152024-08-16 11:16:15

Judging History

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

  • [2024-08-16 11:16:15]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3860kb
  • [2024-08-16 11:16:15]
  • 提交

answer

/*
 * author:  ADMathNoob
 * created: 08/15/24 23:11:42
 * problem: https://qoj.ac/problem/5108
 */

/*
Comments about problem:


*/

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> down(n), up(n);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int mn = 0;
    int sum = 0;
    for (char c : s) {
      int d = (c == '(' ? +1 : -1);
      sum += d;
      mn = min(mn, sum);
    }
    down[i] = mn;
    up[i] = sum + mn;
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return max(down[i], down[i] - up[i] + down[j]) < max(down[j], down[j] - up[j] + down[i]);
  });
  int at = 0;
  for (int i : order) {
    at -= down[i];
    if (at < 0) {
      cout << "impossible\n";
      return 0;
    }
    at += up[i];
  }
  if (at != 0) {
    cout << "impossible\n";
    return 0;
  }
  for (int i : order) {
    cout << i + 1 << '\n';
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 3832kb

input:

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

output:

8378
8776
24534
12662
44055
21747
39764
28445
14821
27739
6827
34130
32506
15706
19829
21673
42674
32495
6916
14047
109
16769
15641
213
31585
38245
25565
36113
46482
11635
20550
6596
7478
633
3201
45612
39663
35457
30675
28930
16420
45933
46182
22204
29415
21519
41410
12925
20200
17735
1425
44459
37...

result:

ok good plan

Test #2:

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

input:

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

output:

537
354
583
904
145
736
159
694
994
480
488
634
519
675
44
53
980
855
745
845
289
660
487
654
275
930
455
218
676
478
353
448
495
38
958
395
167
150
107
317
507
871
436
621
521
661
52
417
776
196
538
141
939
431
78
627
413
72
954
956
132
424
333
346
370
300
194
111
609
321
892
23
946
571
720
717
116...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

1
2

result:

wrong answer wrong plan (expected impossible)