Submission #638093

# Submission time Handle Problem Language Result Execution time Memory
638093 2022-09-04T15:00:18 Z sofijavelkovska Homework (CEOI22_homework) C++14
0 / 100
141 ms 14572 KB
#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() && expression[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];
}

int main()
{
    string expression;
    cin >> expression;
    int index=0, node=0;
    vector<int> adj[100];
    int type[100];
    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

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() && expression[index+1]==',')
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int evalute(int, std::vector<int>*, int*, int*)':
Main.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 14572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -