QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373758 | #5108. Prehistoric Programs | Anish_aak | RE | 12ms | 6536kb | C++14 | 2.7kb | 2024-04-02 04:19:20 | 2024-04-02 04:19:21 |
Judging History
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;
}
詳細信息
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 () ()