Submission #638061

#	Time	Username	Problem	Language	Result	Execution time	Memory
638061		sofijavelkovska	Homework (CEOI22_homework)	C++14	0 / 100	342 ms	281680 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void maketree(int &index, int &node, string &expression, vector<int> adj[], int type[])
{
    if (expression[index]=='?')
    {
        type[node]=3;
        return;
    }
    if (expression.substr(index, 3)=="min")
        type[node]=1;
    else
        type[node]=2;
    int currentnode=node;
    index=index+4;
    node=node+1;
    adj[currentnode].push_back(node);
    maketree(index, node, expression, adj, type);
    while (expression[index]!=',')
        index=index+1;
    index=index+1;
    node=node+1;
    adj[currentnode].push_back(node);
    maketree(index, node, expression, adj, type);
    while (expression[index]!=')')
        index=index+1;
    if (index+1<expression.size() && index+1==',')
    {
        index=index+2;
        node=node+1;
        adj[currentnode].push_back(node);
        maketree(index, node, expression, adj, type);
    }

    return;
}

int evalute(int node, vector<int> adj[], int type[], int value[])
{
    if (type[node]==1)
        return min(evalute(adj[node][0], adj, type, value), evalute(adj[node][1], adj, type, value));
    if (type[node]==2)
        return max(evalute(adj[node][0], adj, type, value), evalute(adj[node][1], adj, type, value));
    if (type[node]==3)
        return value[node];

    return 0;
}

int main()
{
    string expression;
    cin >> expression;
    int index=0, node=0;
    vector<int> adj[1000000];
    int type[1000000];
    maketree(index, node, expression, adj, type);
    int i, j;
    int n=0;
    for (i=0; i<=node; i++)
        if (type[i]==3)
            n=n+1;
    int permutation[n];
    for (i=0; i<n; i++)
        permutation[i]=i+1;
    int value[node+1];
    set<int> possiblevalues;
    do {
        j=0;
        for (i=0; i<=node; i++)
            if (type[i]==3)
            {
                value[i]=permutation[j];
                j=j+1;
            }
        possiblevalues.insert(evalute(0, adj, type, value));
    } while(next_permutation(permutation, permutation+n));
    cout << possiblevalues.size();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void maketree(int&, int&, std::string&, std::vector<int>*, int*)':
Main.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if (index+1<expression.size() && index+1==',')
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

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