Submission #679470

#	Time	Username	Problem	Language	Result	Execution time	Memory
679470		eli82	Homework (CEOI22_homework)	C++14	53 / 100	97 ms	24696 KiB

Main

/* in the name of god */
/* be name khoda */

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define fs first
#define cs second
#define be_fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<ll, ll>
#define all_g(x) x.begin(), x.end(), greater<int>()
#define all(x) x.begin(), x.end()
const ll MAX_N = 1e4 + 24, mod1 = 998244353, mod2 = 1e9 + 7, lg = 21;
/// too gold . . .
/// is
string h;
vector<int>adj[MAX_N];
set<int>dp[MAX_N];
int mark[MAX_N];
vector<int>baga;
int cnt[MAX_N];

int dfs(int a){
    if(h[a] == '?'){
        baga.pb(a);
        cnt[a] = 1;
        return a;
    }
    h[a + 1] == 'i'? mark[a] = 1: mark[a] = 2;
    adj[a].pb(a + 4);
    int x = dfs(a + 4);
    adj[a].pb(x + 2);
    int xx = dfs(x + 2);
    cnt[a] = cnt[a + 4] + cnt[x + 2];
    return xx + 1;
} 

void solve(int a){
    if(h[a] == '?')
        return;
    for(int k :  adj[a]){
        solve(k);
    }
    int u = adj[a][0];
    int v = adj[a][1];
    if(mark[a] == 1){
        for(int i = 1; i <= cnt[a]; i++){
            auto x = (dp[u].upper_bound(i));
            if(x == dp[u].begin())
                continue;
            x--;
            int xx = *x;
            auto p = dp[v].end(); p--;
            int r = cnt[v] - *p + 1;
            r += cnt[u] - xx;
            if(r <= cnt[a] - i){
                dp[a].insert(i);
            }
        }
        for(int i = 1; i <= cnt[a]; i++){
            auto x = (dp[v].upper_bound(i));
            if(x == dp[v].begin())
                continue;
            x--;
            int xx = *x;
            auto p = dp[u].end(); p--;
            int r = cnt[u] - *p + 1;
            r += cnt[v] - xx;
            if(r <= cnt[a] - i){
                dp[a].insert(i);
            }
        }
    }

    else{
        for(int i = 1; i <= cnt[a]; i++){
            int x = *dp[v].begin();
            x = i - x;
            if(x < 0)continue;
            auto p = dp[u].upper_bound(x);
            if(p == dp[u].begin())
                continue;
            p--;
            if(cnt[a] - i >= cnt[u] - *p){
                dp[a].insert(i);
            }
        }
        for(int i = 1; i <= cnt[a]; i++){
            int x = *dp[u].begin();
            x = i - x;
            if(x < 0)continue;
            auto p = dp[v].upper_bound(x);
            if(p == dp[v].begin())
                continue;
            p--;
            if(cnt[a] - i >= cnt[v] - *p){
                dp[a].insert(i);
            }
        }
    }
    return;
}

int main(){
    be_fast 
    cin >> h;
    dfs(0);
    for(int i : baga){
        dp[i].insert(1);
    }
    solve(0);
    cout << dp[0].size() << endl; 
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 13
• Subtask 4: 30 / 30
• Subtask 5: 0 / 34