QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#555843 | #5108. Prehistoric Programs | evirir | WA | 17ms | 10236kb | C++20 | 1.7kb | 2024-09-10 10:54:17 | 2024-09-10 10:54:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
using ll = long long;
using ii = pair<ll, ll>;
using ld = long double;
struct St
{
string s;
int id;
int net;
int mn;
auto operator<=>(const St& o) const
{
return tie(mn, net) <=> tie(o.mn, o.net);
}
};
void fail()
{
cout<<"impossible\n";
exit(0);
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n; cin>>n;
vector<St> a(n);
forn(i,0,n)
{
string s; cin>>s;
int sum = 0;
int mn = 0;
for (const auto c : s)
{
if (c == '(') sum++;
else sum--;
mn = min(mn, sum);
}
a[i] = {s, i, sum, mn};
}
vector<St> a0 = a;
sort(all(a));
vector<int> ans;
ans.reserve(n);
priority_queue<ii, vector<ii>> q; // (net, id)
int sum = 0;
int p = n - 1; // last unused
while (sz(ans) < n)
{
while (p >= 0 && sum + a[p].mn >= 0)
{
q.push({a[p].net, a[p].id});
p--;
}
if (q.empty()) fail();
auto [net, id] = q.top(); q.pop();
ans.pb(id);
sum += net;
}
sum = 0;
forn(i,0,n)
{
int mn = a0[ans[i]].mn;
int net = a0[ans[i]].net;
if (sum + mn < 0) fail();
sum += net;
}
if (sum != 0) fail();
forn(i, 0, n) cout << ans[i] + 1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 17ms
memory: 10236kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
impossible
result:
wrong answer you didn't find a solution but jury did