oj.uz

Submission #702600

# Submission time Handle Problem Language Result Execution time Memory
702600 2023-02-24T13:52:29 Z WeIlIaN Homework (CEOI22_homework) C++14
0 / 100
 157 ms 133124 KB 
#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;
      |         ^

Subtask #1
0 / 10.0

# 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 -

Subtask #2
0 / 13.0

# 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 -

Subtask #3
0 / 13.0

# 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 -

Subtask #4
0 / 30.0

# 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 -

Subtask #5
0 / 34.0

# 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 -