Submission #1205174

#TimeUsernameProblemLanguageResultExecution timeMemory
1205174MighilonHomework (CEOI22_homework)C++20
100 / 100
101 ms77836 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const int MOD = 1e9 + 7; struct node{ int type,l=-1,r=-1; }; int cnt=0; node t[(int)2e6+10]; int le=0; string s; void dfs(int& i,int tp){ int c=0, x=cnt; t[x].type=tp; dbg(x,tp) if(tp==2) return; for(;i<sz(s);){ dbg(x,i) int type=-1; if(s[i]=='i') type=0; else if(s[i]=='x') type=1; else if(s[i]=='?'){ dbg(i) type=2; } if(type!=-1){ if(c==0){ t[x].l=++cnt; dfs(++i,type); } else{ t[x].r=++cnt; dfs(++i,type); } c++; //--- if(type==2) le++; } if(c==2){ // i++; break; } if(type==-1) i++; } } vi lf; int c=0; int dfs2(int x){ int l=-1,r=-1; if(t[x].l!=-1){ l=dfs2(t[x].l); } if(t[x].r!=-1){ r=dfs2(t[x].r); } if(t[x].type==0) return min(l,r); else if(t[x].type==1) return max(l,r); else { return lf[c++]; } } int ans=0; pi dfs3(int x){ pi l,r; if(t[x].l!=-1){ l=dfs3(t[x].l); } if(t[x].r!=-1){ r=dfs3(t[x].r); } if(t[x].type==0) return {min(l.f,r.f),l.s+r.s+1}; else if(t[x].type==1) return {l.f+r.f+1,min(l.s,r.s)}; else return {0,0}; } void solve(){ cin>>s; F0R(i,sz(s)){ if(s[i]=='i'){ dfs(++i,0); break; } else if(s[i]=='x'){ dfs(++i,1); break; } } // dbg(cnt) // F0R(i,cnt){ // cout<<i<<" "<<t[i].type<<" "<<t[i].l<<" "<<t[i].r<<nl; // } // lf.resize(le); // iota(all(lf),1); // set<int> st; // dbg(le) // // int cc=1; // do{ // c=0; // st.insert(dfs2(0)); // }while(next_permutation(all(lf))); // dbg(st) // cout<<le<<nl; // cout<<sz(st)<<nl; pi ans=dfs3(0); cout<<le-ans.f-ans.s<<nl; } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int TC = 1; // cin >> TC; while(TC--){ solve(); } return 0; }
#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...