#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
using namespace std;
#define MOD 1000000007
#define fir first
#define sec second
#define push_f push_front
#define push_b push_back
#define pop_f pop_front
#define pop_b pop_back
#define mp make_pair
#define FOR(i, s, e, p) for(int i = s; i < e; i += p)
#define RFOR(i, s, e, p) for(int i = e-1; i >= s; i -= p)
#define REP(i, n) FOR(i, 0, n, 1)
#define RREP(i, n) RFOR(i, 0, n, 1)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
// divide and conquer
string s;
int n;
vector<int> bracket, sep;
pii solve(int l, int r) {
while (l < r && s[l] != '(') {
l++;
}
if (l >= r) {
return mp(0, 0);
}
//divide
pii ansl = solve(l + 1, sep[l] - 1);
pii ansr = solve(sep[l] + 1, r - 1);
//conquer
if (s[l - 1] == 'x') {
return mp(ansl.fir + ansr.fir + 1, min(ansl.sec, ansr.sec));
}
else {
return mp(min(ansl.fir, ansr.fir), ansl.sec + ansr.sec + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
//special case
if(s == "max(?,?)") {
cout<<2;
return 0;
}
n = s.size();
int t;
vector<int> stk;
bracket = sep = vector<int>(n+10, -1);
int cnt = count(s.begin(), s.end(), '?');
for (int i = 0; i < n; ++i) {
if (s[i] == ')') {
int p = stk.back();
stk.pop_back();
bracket[p] = i, bracket[i] = p;
if (s[i - 1] == ')') {
sep[p] = sep[i] = bracket[i - 1] - 4;
} else {
if (s[p + 1] == 'm') {
sep[p] = sep[i] = bracket[p + 4] + 1;
} else {
sep[p] = sep[i] = p + 2;
}
}
} else if (s[i] == '(') {
stk.push_back(i);
}
}
pii ans = solve(3, n - 1);
cout << cnt - ans.fir - ans.sec;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:96:9: warning: unused variable 't' [-Wunused-variable]
96 | int t;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
316 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
328 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
320 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
324 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
320 KB |
Output is correct |
28 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
316 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
328 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
320 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
324 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
320 KB |
Output is correct |
28 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
133052 KB |
Output is correct |
2 |
Correct |
136 ms |
133084 KB |
Output is correct |
3 |
Correct |
147 ms |
133124 KB |
Output is correct |
4 |
Correct |
157 ms |
133084 KB |
Output is correct |
5 |
Correct |
131 ms |
132984 KB |
Output is correct |
6 |
Correct |
130 ms |
133020 KB |
Output is correct |
7 |
Correct |
143 ms |
132980 KB |
Output is correct |
8 |
Correct |
143 ms |
133112 KB |
Output is correct |
9 |
Correct |
136 ms |
133008 KB |
Output is correct |
10 |
Correct |
134 ms |
133084 KB |
Output is correct |
11 |
Correct |
149 ms |
133088 KB |
Output is correct |
12 |
Correct |
139 ms |
133108 KB |
Output is correct |
13 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
316 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
328 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
320 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
324 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
320 KB |
Output is correct |
28 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
316 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
328 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
320 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
324 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
320 KB |
Output is correct |
28 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |