#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 5e3 + 5;
int n, r, cnt;
string s;
int adj[MXN][2];
array<int, 2> dp[MXN];
int sz[MXN];
int t[MXN];
vector<int> R;
array<int, 2> MERGE(array<int, 2> x, array<int, 2> y)
{
return {min(x[0], y[0]), max(x[1], y[1])};
}
void dfs(int a)
{
if (t[a] == 2)
{
dp[a] = {1, 1};
sz[a] = 1;
return;
}
dfs(adj[a][0]), dfs(adj[a][1]);
if (t[a] == 1)
{
dp[a] = MERGE({dp[adj[a][0]][0] + dp[adj[a][1]][0], dp[adj[a][0]][1] + sz[adj[a][1]]}, {dp[adj[a][1]][0] + dp[adj[a][0]][0], dp[adj[a][1]][1] + sz[adj[a][0]]});
}
else
{
dp[a] = MERGE({dp[adj[a][0]][0], dp[adj[a][0]][1] + dp[adj[a][1]][1] - 1}, {dp[adj[a][1]][0], dp[adj[a][1]][1] + dp[adj[a][0]][1] - 1});
}
sz[a] = sz[adj[a][0]] + sz[adj[a][1]];
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n = s.length();
string nw;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == ',') continue;
if (s[i] == '?')
{
t[nw.size()] = 2;
nw.push_back('(');
nw.push_back(')');
}
else if (s[i] == '(' || s[i] == ')') nw.push_back(s[i]);
else
{
if (s[i + 1] == 'i') t[nw.size()] = 0;
else t[nw.size()] = 1;
i += 2;
}
}
vector<int> v;
R.assign(nw.size(), 0);
for (int i = (int)nw.size() - 1; i >= 0; i--)
{
if (nw[i] == ')') v.push_back(i);
else R[i] = v.back(), v.pop_back();
}
cout << nw << '\n';
v.clear();
for (int i = (int)nw.size() - 1; i >= 0; i--)
{
if (nw[i] == '(')
{
vector<int> tmp;
while (!v.empty() && v.back() <= R[i]) tmp.push_back(v.back()), v.pop_back();
assert(tmp.size() == 2 || tmp.empty());
v.push_back(i);
if (tmp.size() == 2)
{
adj[i][0] = tmp[0], adj[i][1] = tmp[1];
}
}
}
assert(v.size() == 1);
dfs(v[0]);
cout << dp[v[0]][1] - dp[v[0]][0] + 1 << '\n';
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < s.length(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
14816 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
