Submission #725946

#	Time	Username	Problem	Language	Result	Execution time	Memory
725946		amunduzbaev	Homework (CEOI22_homework)	C++17	100 / 100	148 ms	147316 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	string s; cin >> s;
	int n = 0;
	vector<int> ss, t, par;
	for(int i=0;i<(int)s.size();i++){
		if(s[i] == '?'){
			n++;
		}
		if(s[i] == '('){
			t.push_back(s[i-1] == 'x');
			ss.push_back(par.size());
			par.push_back(0);
		}
		if(s[i] == ')'){
			par[ss.back()] = par.size();
			ss.pop_back();
		}
	}
	
	int sz = par.size();
	par.push_back(sz);
	function<ar<int, 2>(int, int)> get = [&](int l, int r) -> ar<int, 2>{
		if(l >= r){
			return {1, 1};
		}
		if(l + 1 == r){
			return (ar<int, 2>){1 + t[l], 1 + (!t[l])};
		}
		int mn = 0, mx = 0;
		ar<int, 2> L = get(l + 1, par[l + 1]), R = get(par[l + 1], r);
		if(t[l]){
			mx = min(L[1], R[1]);
			mn = L[0] + R[0];
		} else {
			mx = L[1] + R[1];
			mn = min(L[0], R[0]);
		}
		//~ cout<<l<<" "<<r<<" "<<mn<<" "<<mx<<endl;
		return (ar<int, 2>){mn, mx};
	};
	
	ar<int, 2> res = get(0, sz);
	int l = res[0], r = n - res[1] + 1;
	cout<<r - l + 1<<"\n";
}

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