Submission #848552

#	Time	Username	Problem	Language	Result	Execution time	Memory
848552		Benmath	Homework (CEOI22_homework)	C++14	100 / 100	177 ms	46340 KiB

Main

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

int main()
{
  string s;
  cin>>s;
  int n=0;
  for(int i=0;i<s.size();i++){
      if(s[i]=='?'){
          n++;
      }
  }
  stack<int>type;
  stack<int>zagrade;
  pair<int,int> prvi[n+1];
  pair<int,int> drugi[n+1];
  int broj_prvi[n+1];
  int broj_drugi[n+1];
  for(int i=0;i<=n;i++){
      prvi[i]= {-1,-1};
      drugi[i]= {-1,-1};
broj_prvi[i]=0;
broj_drugi[i]=0;
  }
  int bro=0;
  for(int i=0;i<s.size();i++){
      if(s[i]=='('){
          if(s[i-1]=='n'){
              type.push(0);
              zagrade.push(bro);
              bro++;
          }else{
              type.push(1);
              zagrade.push(bro);
              bro++;
          }
      }else if(s[i]=='?'){
          int tren = zagrade.top();
          if(broj_prvi[tren]==0){
              prvi[tren]={1,1};
              broj_prvi[tren]=1;
          }else{
              drugi[tren]={1,1};
              broj_drugi[tren]=1;
          }
      }else{
          if(s[i]==')'){
              int tren=zagrade.top();
          int l1=0;
          int r1=0;
          int so=0;
          if(type.top()==0){
              l1=min(prvi[tren].first,drugi[tren].first);
              r1=prvi[tren].second+drugi[tren].second-1;
              so=broj_drugi[tren]+broj_prvi[tren];
          }else{
              l1=prvi[tren].first+drugi[tren].first;
              r1=max(broj_drugi[tren]+prvi[tren].second,broj_prvi[tren]+drugi[tren].second);
              so=broj_drugi[tren]+broj_prvi[tren];
              
          }
          zagrade.pop();
          type.pop();
          if(zagrade.empty()){
              cout<<r1-l1+1;
              return 0;
          }
          tren=zagrade.top();
          if(broj_prvi[tren]==0){
              prvi[tren]={l1,r1};
              broj_prvi[tren]=so;
          }else{
              drugi[tren]={l1,r1};
              broj_drugi[tren]=so;
          }
          }
      }
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i=0;i<s.size();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