Submission #1111689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111689		noyancanturk	Homework (CEOI22_homework)	C++17	100 / 100	475 ms	149408 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;

int n=0;
string s;
unordered_map<int,int>part;

pii parse(int l,int r){
  if(l==r){
    return {1,1};
  }
  int com=-1;
  if(s[l+4]=='?')com=l+5;
  else com=part[l+7]+1;
  pii res1=parse(l+4,com-1),res2=parse(com+1,r-1);
  pii res;
  if(s[l+1]=='a'){
    res.first=res1.first+res2.first;
    res.second=min(res1.second,res2.second);
  }else{
    res.second=res1.second+res2.second;
    res.first=min(res1.first,res2.first);
  }
  return res;
}
int main(){
  #ifdef Local
  freopen(".in","r",stdin);
  freopen(".out","w",stdout);
  #endif
  cin>>s;
  for(int i=0;i<s.size();i++)n+=s[i]=='?';
  stack<int>inds;
  for(int i=0;i<s.size();i++){
    if(s[i]=='('){
      inds.push(i);
    }else if(s[i]==')'){
      part[inds.top()]=i;
      inds.pop();
    }
  }
  pii res=parse(0,s.size()-1);
  cout<<n-res.second-res.first+2;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<s.size();i++)n+=s[i]=='?';
      |               ~^~~~~~~~~
Main.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=0;i<s.size();i++){
      |               ~^~~~~~~~~

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