Submission #702600

#	Time	Username	Problem	Language	Result	Execution time	Memory
702600		WeIlIaN	Homework (CEOI22_homework)	C++14	0 / 100	157 ms	133124 KiB

Main

#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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:96:9: warning: unused variable 't' [-Wunused-variable]
   96 |     int t;
      |         ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 30
• Subtask 5: 0 / 34