Submission #705458

#	Time	Username	Problem	Language	Result	Execution time	Memory
705458		krizsu222	Homework (CEOI22_homework)	C++17	10 / 100	1063 ms	187844 KiB

Main

#include "bits/stdc++.h"
#define ls (v * 2)
#define rs (v * 2 + 1)
#define TREE_SIZE (1<<20)
using namespace std;

struct node
{
    string type;
    int value;
} tree[TREE_SIZE * 2];
string s;
int res;
int const maxn = 1e6 + 3;
bool ok[maxn];

void insert(int v, int val)
{
    //v += TREE_SIZE;
    tree[v].value = val;
    while(v != 0)
    {
        v /= 2;     
        if(tree[v].type == "min")
        {
            if(tree[rs].value == 0) tree[v].value = tree[ls].value;
            else tree[v].value = min(tree[ls].value, tree[rs].value);
        }
        if(tree[v].type == "max")
        {
            if(tree[rs].value == 0) tree[v].value = tree[ls].value;
            else tree[v].value = max(tree[ls].value, tree[rs].value);
        }
    }
}

signed main()
{
    cin.tie(0) -> ios_base::sync_with_stdio(0);
    cout.tie(0) -> ios_base::sync_with_stdio(0);

    cin >> s;
    int question_marks = 0;
    for(auto u : s)
        if(u == '?')
            question_marks++;
    vector <int> q;
    string temp = "";
    int it = 1, son = 0, lastfunc = 0;
    for(int i = 0; i < s.length(); ++i)
    {
        if(s[i] == 'm' || s[i] == 'i' || s[i] == 'a') continue;
        if(s[i] == '(') it *= 2;
        if(s[i] == ')') it /= 2;
        it += son;
        int act_son = it;
        if(s[i] == ',') son = 1;
        else son = 0;
        if(s[i] == 'n')
            tree[act_son].type = "min";
        if(s[i] == 'x')
            tree[act_son].type = "max";
        if(s[i] == '?')
        {
            tree[act_son].type = "const";
            q.push_back(act_son);
        }
    }
    // for(auto u : q)
    //     cout << u << ' ';
    vector <int> perms(question_marks);
    for(int i = 0; i < question_marks; ++i)
        perms[i] = i + 1;
    do
    {
        for(int i = 0; i < question_marks; ++i)
            insert(q[i], perms[i]);
        ok[tree[1].value] = true; 
        //cout << tree[1].value << '\n';
    } while(next_permutation(perms.begin(), perms.end()));
    for(int i = 1; i <= question_marks; ++i)
        if(ok[i] == true)
            res++;
    cout << res;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < s.length(); ++i)
      |                    ~~^~~~~~~~~~~~
Main.cpp:49:26: warning: unused variable 'lastfunc' [-Wunused-variable]
   49 |     int it = 1, son = 0, lastfunc = 0;
      |                          ^~~~~~~~

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