Submission #696964

#TimeUsernameProblemLanguageResultExecution timeMemory
696964DeepessonHomework (CEOI22_homework)C++17
53 / 100
167 ms25680 KiB
#include <bits/stdc++.h> #define MAX 105005 typedef std::pair<int,int> pii; ///Garantido que con=2 std::vector<int> con[MAX]; int types[MAX]; enum tipos {MINIMO=1,MAXIMO}; int N; int rodada=42; ///0 -> Menor que objetivo ///1 -> Maior que objetivo int turno[MAX][2]; int tab[MAX][2]; int dp(int pos,int modo){ if(!types[pos]){///Folha return 1; } if(turno[pos][modo]==rodada)return tab[pos][modo]; turno[pos][modo]=rodada; int ans=1e9; ///Procurando valores menores que objetivo if(modo==0){ if(types[pos]==MINIMO){ ans=std::min(ans,dp(con[pos][0],modo)); ans=std::min(ans,dp(con[pos][1],modo)); }else { ans=dp(con[pos][0],modo)+dp(con[pos][1],modo); } ///Procurando valores maiores que objetivo }else { if(types[pos]==MINIMO){ ans=dp(con[pos][0],modo)+dp(con[pos][1],modo); }else { ans=std::min(ans,dp(con[pos][0],modo)); ans=std::min(ans,dp(con[pos][1],modo)); } } return tab[pos][modo]=ans; } ///Left -> valores menores que obj, Right -> valores maiores que obj int left,right,objetivo; int marcas[MAX]; void dfs(int pos){ if(!types[pos]){///Eh folha int inicio=left+1; int fim = (N-right); marcas[inicio]++; marcas[fim+1]--; return; } if(types[pos]==MINIMO){///Temos que ter um valor = X e outro maior que X int esq = dp(con[pos][0],1),dir = dp(con[pos][1],1); right+=esq; dfs(con[pos][1]); right+=-esq+dir; dfs(con[pos][0]); right+=-dir; }else if(types[pos]==MAXIMO){///Temos que ter um valor = X e outro menor que X int esq = dp(con[pos][0],0),dir = dp(con[pos][1],0); left+=esq; dfs(con[pos][1]); left+=-esq+dir; dfs(con[pos][0]); left+=-dir; } return; } int main() { std::string s; std::cin>>s; for(auto&x:s)if(x=='?')++N; ///Destrinchar std::vector<int> stack; int cur=0; for(int i=0;i<s.size();++i){ if(s[i]==',')continue; if(s[i]==')'){ stack.pop_back(); continue; } if(s[i]=='?'){ con[stack.back()].push_back(cur); ++cur; continue; } if(s[i]=='m'){ if(stack.size()) con[stack.back()].push_back(cur); int tipo=MINIMO; if(s[i+1]=='a')tipo=MAXIMO; i+=3; stack.push_back(cur); types[cur]=tipo; ++cur; }else std::cout<<s[i]; } dfs(0); int count=0,curs=0; for(int i=1;i<=N;++i){ curs+=marcas[i]; if(curs)++count; } std::cout<<count<<"\n"; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<s.size();++i){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...