This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
const int mxn = 1e6+10;
vector<int> tree[mxn*2];
int val[mxn*2],dp[mxn*2];
int vcnt = 0;
int N;
string s;
int rt;
void dfs(int now){
if(val[now]<0)dp[now] = (val[now] == -1?mxn:-mxn);
else dp[now] = val[now];
for(auto nxt:tree[now]){
dfs(nxt);
if(val[now] == -2)dp[now] = max(dp[now],dp[nxt]);
else dp[now] = min(dp[now],dp[nxt]);
}
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>s;
for(int i = 0;i<s.size();i++)N += s[i] == '?';
{
int pt = 0;
vector<int> v,stk;
while(pt<s.size()){
if(s[pt] == 'm'){
if(s.substr(pt,3) == "min"){
v.push_back(-1);
}
else{
v.push_back(-2);
}
pt += 3;
}
else if(s[pt] == '?'){
v.push_back(++vcnt);
pt++;
}
else pt++;
}
vcnt = N;
for(auto &i:v){
stk.push_back(i);
while(stk.size()>=2&&stk.end()[-1]>0&&stk.end()[-2]>0){
int a = stk.end()[-1],b = stk.end()[-2];
stk.pop_back();stk.pop_back();
int c = ++vcnt;
tree[c].push_back(a);
tree[c].push_back(b);
assert(stk.back()<0);
val[c] = stk.back();
stk.pop_back();
rt = c;
stk.push_back(c);
}
}
}
dfs(rt);
for(int i = 1;i<=N;i++)val[i] = i;
set<int> st;
if(N>10)return 0;
do{
dfs(rt);
st.insert(dp[rt]);
}while(next_permutation(val+1,val+N+1));
vector<int> vv;
for(auto &i:st)vv.push_back(i);
for(int i = 1;i<vv.size();i++){
assert(vv[i] == vv[i-1]+1);
}
cout<<st.size()<<'\n';
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0;i<s.size();i++)N += s[i] == '?';
| ~^~~~~~~~~
Main.cpp:32:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while(pt<s.size()){
| ~~^~~~~~~~~
Main.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 1;i<vv.size();i++){
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |