Submission #1254339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254339		Jovica	Homework (CEOI22_homework)	C++20	23 / 100	184 ms	81328 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6+1;
struct Node{
    int levo=-1,desno=-1;
    bool b = false;
};
vector<Node> drvo;
string s;
int pozicija;
int ss[maxn];

void izgradi()
{
    Node prazno;drvo.push_back(prazno);
    int p = drvo.size()-1;
    while (pozicija < s.size())
    {
        char c = s[pozicija];if (c == 'm' || c == 'i' || c == 'n' || c=='x') pozicija++;
        if (c == 'a') drvo[p].b = true,pozicija++;
        if (c == '?' || c == ')') {
            pozicija++;break;
        }
        if (c == '('){
            drvo[p].levo = drvo.size();
            pozicija++;
            izgradi();
        }
        if (c == ','){
            drvo[p].desno = drvo.size();
            pozicija++;
            izgradi();
        }
    }
    if (drvo[p].levo == -1) ss[p] = 1;
    else ss[p] = ss[drvo[p].levo]+ss[drvo[p].desno];
}

int dp[50][66000][2];
bool visited[50][66000];
int n;

int vidi(int m)
{
    int k = 0;
    while (m%2==0){
        k++;m/=2;
    }

    return k;
}

vector<vector<int> > bit;

void f(int p,int mask)
{
    //cout<<"p = "<<p<<" mask="<<mask<<endl;
    //system("pause");
    if (visited[p][mask]) return;
    if (ss[p] == 1) {
        dp[p][mask][0] = dp[p][mask][1] = vidi(mask);
        //cout<<"dp["<<p<<"]["<<mask<<"] = "<<vidi(mask)<<endl;
        return;
    }
    //cout<<"mine\n";

    int mal = 20,gol = -1;

    int l = drvo[p].levo,r = drvo[p].desno;
    for (auto a: bit[ss[l]])
    {
        int b = mask ^ a;
        if ((a|b) != mask) continue;
        //cout<<mask<<" go dele "<<a<<" "<<b<<endl;
        f(l,a);
        f(r,b);

        if (drvo[p].b)
        {
            mal = min(mal, max(dp[l][a][0],dp[r][b][0]));
            gol = max(gol, max(dp[l][a][1],dp[r][b][1]));
        }
        else
        {
            mal = min(mal, min(dp[l][a][0],dp[r][b][0]));
            gol = max(gol, min(dp[l][a][1],dp[r][b][1]));
        }
    }

    dp[p][mask][0] = mal;
    dp[p][mask][1] = gol;
    visited[p][mask] = true;
    //cout<<"dp["<<p<<"]["<<mask<<"] = "<<mal<<", "<<gol<<endl;
}

int main()
{ios_base::sync_with_stdio(false);cin.tie();cout.tie(0);

    cin>>s;
    izgradi();

    //for(auto a: drvo) cout<<a.levo<<" "<<a.desno<<" "<<a.b<<endl;

    //for (int i=0;i<drvo.size();i++) cout<<ss[i]<<" ";cout<<endl;

    for (int i=0;i<drvo.size();i++) if (ss[i]==1) n++;

    for (int i=0;i<(1<<n);i++){
        int p = __builtin_popcount(i);
        while (p >= bit.size()) bit.push_back({});
        bit[p].push_back(i);
    }

    f(0,(1<<n)-1);
    cout<<dp[0][(1<<n) -1][1] - dp[0][(1<<n) -1][0] +1 <<endl;
    return 0;
}

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