oj.uz

Submission #638059

# Submission time Handle Problem Language Result Execution time Memory
638059 2022-09-04T13:26:17 Z sofijavelkovska Homework (CEOI22_homework) C++14
0 / 100
 166 ms 19488 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() && 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[1000];
    int type[1000];
    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() && 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 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 212 KB Output is correct
2 Correct 42 ms 304 KB Output is correct
3 Correct 36 ms 212 KB Output is correct
4 Correct 32 ms 212 KB Output is correct
5 Correct 35 ms 304 KB Output is correct
6 Correct 35 ms 308 KB Output is correct
7 Correct 33 ms 212 KB Output is correct
8 Correct 34 ms 304 KB Output is correct
9 Correct 32 ms 212 KB Output is correct
10 Correct 39 ms 312 KB Output is correct
11 Correct 32 ms 212 KB Output is correct
12 Correct 40 ms 300 KB Output is correct
13 Correct 42 ms 212 KB Output is correct
14 Runtime error 2 ms 596 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 212 KB Output is correct
2 Correct 42 ms 304 KB Output is correct
3 Correct 36 ms 212 KB Output is correct
4 Correct 32 ms 212 KB Output is correct
5 Correct 35 ms 304 KB Output is correct
6 Correct 35 ms 308 KB Output is correct
7 Correct 33 ms 212 KB Output is correct
8 Correct 34 ms 304 KB Output is correct
9 Correct 32 ms 212 KB Output is correct
10 Correct 39 ms 312 KB Output is correct
11 Correct 32 ms 212 KB Output is correct
12 Correct 40 ms 300 KB Output is correct
13 Correct 42 ms 212 KB Output is correct
14 Runtime error 2 ms 596 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 19488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 212 KB Output is correct
2 Correct 42 ms 304 KB Output is correct
3 Correct 36 ms 212 KB Output is correct
4 Correct 32 ms 212 KB Output is correct
5 Correct 35 ms 304 KB Output is correct
6 Correct 35 ms 308 KB Output is correct
7 Correct 33 ms 212 KB Output is correct
8 Correct 34 ms 304 KB Output is correct
9 Correct 32 ms 212 KB Output is correct
10 Correct 39 ms 312 KB Output is correct
11 Correct 32 ms 212 KB Output is correct
12 Correct 40 ms 300 KB Output is correct
13 Correct 42 ms 212 KB Output is correct
14 Runtime error 2 ms 596 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 212 KB Output is correct
2 Correct 42 ms 304 KB Output is correct
3 Correct 36 ms 212 KB Output is correct
4 Correct 32 ms 212 KB Output is correct
5 Correct 35 ms 304 KB Output is correct
6 Correct 35 ms 308 KB Output is correct
7 Correct 33 ms 212 KB Output is correct
8 Correct 34 ms 304 KB Output is correct
9 Correct 32 ms 212 KB Output is correct
10 Correct 39 ms 312 KB Output is correct
11 Correct 32 ms 212 KB Output is correct
12 Correct 40 ms 300 KB Output is correct
13 Correct 42 ms 212 KB Output is correct
14 Runtime error 2 ms 596 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -