oj.uz

Submission #638060

# Submission time Handle Problem Language Result Execution time Memory
638060 2022-09-04T13:30:26 Z sofijavelkovska Homework (CEOI22_homework) C++14
0 / 100
 356 ms 281428 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[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

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 50 ms 27680 KB Output is correct
2 Correct 50 ms 27612 KB Output is correct
3 Correct 47 ms 27580 KB Output is correct
4 Correct 51 ms 27604 KB Output is correct
5 Correct 47 ms 27604 KB Output is correct
6 Correct 48 ms 27664 KB Output is correct
7 Correct 52 ms 27604 KB Output is correct
8 Correct 49 ms 27580 KB Output is correct
9 Correct 46 ms 27604 KB Output is correct
10 Correct 52 ms 27672 KB Output is correct
11 Correct 47 ms 27664 KB Output is correct
12 Correct 49 ms 27676 KB Output is correct
13 Correct 48 ms 27680 KB Output is correct
14 Runtime error 50 ms 55996 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 50 ms 27680 KB Output is correct
2 Correct 50 ms 27612 KB Output is correct
3 Correct 47 ms 27580 KB Output is correct
4 Correct 51 ms 27604 KB Output is correct
5 Correct 47 ms 27604 KB Output is correct
6 Correct 48 ms 27664 KB Output is correct
7 Correct 52 ms 27604 KB Output is correct
8 Correct 49 ms 27580 KB Output is correct
9 Correct 46 ms 27604 KB Output is correct
10 Correct 52 ms 27672 KB Output is correct
11 Correct 47 ms 27664 KB Output is correct
12 Correct 49 ms 27676 KB Output is correct
13 Correct 48 ms 27680 KB Output is correct
14 Runtime error 50 ms 55996 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 356 ms 281428 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 50 ms 27680 KB Output is correct
2 Correct 50 ms 27612 KB Output is correct
3 Correct 47 ms 27580 KB Output is correct
4 Correct 51 ms 27604 KB Output is correct
5 Correct 47 ms 27604 KB Output is correct
6 Correct 48 ms 27664 KB Output is correct
7 Correct 52 ms 27604 KB Output is correct
8 Correct 49 ms 27580 KB Output is correct
9 Correct 46 ms 27604 KB Output is correct
10 Correct 52 ms 27672 KB Output is correct
11 Correct 47 ms 27664 KB Output is correct
12 Correct 49 ms 27676 KB Output is correct
13 Correct 48 ms 27680 KB Output is correct
14 Runtime error 50 ms 55996 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 50 ms 27680 KB Output is correct
2 Correct 50 ms 27612 KB Output is correct
3 Correct 47 ms 27580 KB Output is correct
4 Correct 51 ms 27604 KB Output is correct
5 Correct 47 ms 27604 KB Output is correct
6 Correct 48 ms 27664 KB Output is correct
7 Correct 52 ms 27604 KB Output is correct
8 Correct 49 ms 27580 KB Output is correct
9 Correct 46 ms 27604 KB Output is correct
10 Correct 52 ms 27672 KB Output is correct
11 Correct 47 ms 27664 KB Output is correct
12 Correct 49 ms 27676 KB Output is correct
13 Correct 48 ms 27680 KB Output is correct
14 Runtime error 50 ms 55996 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -