Submission #729642

#	Time	Username	Problem	Language	Result	Execution time	Memory
729642		Cutebol	Homework (CEOI22_homework)	C++17	53 / 100	175 ms	38664 KiB

Main

#include <bits/stdc++.h>
   
using namespace std;
#define Nahida ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define int long long

const int N = 1e6 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e17 ;

int n ;
int mid[N] ;
string s ;

int mx( int l , int r ){
	
	if ( l == r ) return 1 ;
	int ll = mid[l] ;
	int cl = mx ( l+4 , ll-1 ) ;
	int cr = mx ( ll+1 , r-1 ) ;
	if ( s[l+1] == 'i' ) return cl + cr ;
	else return min( cl , cr ) ;
	
}

int mn( int l , int r ){
	
	if ( l == r ) return 1 ;
	int ll = l+3 , cnt = 0 ;
	while ( ll ++ ){
		if ( s[ll] == '(' ) cnt ++ ;
		if ( s[ll] == ')' ) cnt -- ;
		if ( s[ll] == ',' && cnt == 0 ) break ;
	}
	int cl = mn ( l+4 , ll-1 ) ;
	int cr = mn ( ll+1 , r-1 ) ;
	if ( s[l+1] == 'a' ) return cl + cr ;
	else return min( cl , cr ) ;
	
}

signed main(){
	
//	Nahida ;
	cin >> s ;
	for ( int i = 0 ; i < s.size() ; i ++ )	if ( s[i] == '?' ) n ++ ;
	int cnt = 0 ;
	stack <int> st ;
	for ( int i = 0 ; i < s.size() ; i ++ ){
		if ( s[i] == 'm' ) st.push(i) ;
		if ( s[i] == ',' ){
			mid[st.top()] = i ;
			st.pop() ;
		}
	}
	int l = mn( 0 , s.size() - 1 ) ;
	int r = n-mx( 0 , s.size() - 1 )+1 ;
//	cout << l << ' ' << r << endl ;
	cout << r - l + 1 ;
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:46:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for ( int i = 0 ; i < s.size() ; i ++ ) if ( s[i] == '?' ) n ++ ;
      |                    ~~^~~~~~~~~~
Main.cpp:49:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for ( int i = 0 ; i < s.size() ; i ++ ){
      |                    ~~^~~~~~~~~~
Main.cpp:47:6: warning: unused variable 'cnt' [-Wunused-variable]
   47 |  int cnt = 0 ;
      |      ^~~

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