Submission #702602

#	Time	Username	Problem	Language	Result	Execution time	Memory
702602		WeIlIaN	Homework (CEOI22_homework)	C++14	100 / 100	106 ms	108180 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> 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;
    n = s.size();
    int t;
    stack<int> sta;
    sep = vector<int>(n+10, -1);
    int cnt = count(s.begin(), s.end(), '?');
    REP(i, n) {
        if (s[i] == ')') {
            t = sta.top();
            sta.pop();
            sep[i] = sep[t];
        } else if (s[i] == '(') {
            sta.push(i);
        }
        else if(s[i] == ',') {
            sep[sta.top()] = i;
        }
    }
    pii ans = solve(3, n - 1);
    cout << cnt - ans.fir - ans.sec;
    return 0;
}

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