# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1034972 | pcc | Homework (CEOI22_homework) | C++17 | 224 ms | 186264 KiB |
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));
cout<<st.size()<<'\n';
return 0;
}
Compilation message (stderr)
# | 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... |