QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#141003#4400. Homeworkmohos_risitas10 60ms3564kbC++142.6kb2023-08-17 05:26:562023-08-17 05:26:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-17 05:26:57]
  • 评测
  • 测评结果:10
  • 用时:60ms
  • 内存:3564kb
  • [2023-08-17 05:26:56]
  • 提交

answer

#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>

using namespace std;

int find_comma(int begin, string &expression) {
    int level = 0;
    
    for (int i = begin; i < expression.size(); ++i) {
        if (expression[i] == '(') {
            ++level;
        } else if (expression[i] == ')') {
            --level;
        }

        if (level == 0 && expression[i + 1] == ',') {
            return i + 1;
        }
    }
}

int evaluate(int i, int j, string &expression) {
    if (j - i == 1) {
        return (int)(expression[i] - '0');
    }
    
    // cout << i << " " << j << endl;
    int comma_location = find_comma(i + 4, expression);
    // cout << comma_location << endl;
    // return 0; min(?,max(?,?))
    /*if (i > expression.size() || j == 0) {
        return 0;
    }*/
    int first_argument = evaluate(i + 4, comma_location, expression);
    int second_argument = evaluate(comma_location + 1, j - 1, expression);
    
    if (expression[i + 2] == 'n') {        
        return min(first_argument, second_argument);
    } else if (expression[i + 2] == 'x') {
        return max(first_argument, second_argument);
    }
}

int main() {
    string expression;
    cin >> expression;

    vector<int> question_mark_positions;
    for (int i = 0; i < expression.size(); ++i) {
        char ch = expression[i];
        if (ch == '?') {
            question_mark_positions.push_back(i);
        }
    }

    vector<char> question_mark_replacements;
    for (int i = 1; i <= question_mark_positions.size(); ++i) {
        question_mark_replacements.push_back('0' + i); // all of this is valid only because the ? is guaranteed to be a single digit
    }

    int different_outcomes = 0;
    bool seen_outcomes[10];
    for (int i = 0; i < 10; ++i) {
        seen_outcomes[i] = false;
    }

    do {
        for (int i = 0; i < question_mark_positions.size(); ++i) {
            int question_mark_index = question_mark_positions[i];
            char question_mark_replacement = question_mark_replacements[i];

            expression[question_mark_index] = question_mark_replacement;
        }

        //cout << expression << endl;
        int result = evaluate(0, expression.size(), expression);
        // cout << "hia" << endl;
        if (!seen_outcomes[result]) {
            ++different_outcomes;
            seen_outcomes[result] = true;
        }
    } while (false || next_permutation(question_mark_replacements.begin(), question_mark_replacements.end()));

    cout << different_outcomes << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 30ms
memory: 3452kb

input:

min(max(?,max(min(?,min(?,?)),?)),min(max(?,?),max(?,?)))

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 31ms
memory: 3436kb

input:

max(max(?,min(max(?,min(?,?)),?)),max(max(?,?),max(?,?)))

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 30ms
memory: 3512kb

input:

min(min(min(?,min(?,?)),min(?,?)),min(?,min(min(?,?),?)))

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 26ms
memory: 3504kb

input:

max(max(max(?,?),?),max(max(?,?),min(max(?,?),max(?,?))))

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 28ms
memory: 3492kb

input:

min(max(?,min(?,?)),max(min(max(?,?),?),min(max(?,?),?)))

output:

6

result:

ok single line: '6'

Test #6:

score: 0
Accepted
time: 28ms
memory: 3544kb

input:

max(max(?,min(max(?,?),?)),max(max(max(?,?),min(?,?)),?))

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 30ms
memory: 3472kb

input:

min(min(max(min(?,?),?),?),min(?,max(max(?,?),min(?,?))))

output:

6

result:

ok single line: '6'

Test #8:

score: 0
Accepted
time: 42ms
memory: 3500kb

input:

min(min(min(min(?,?),max(?,?)),min(min(?,?),min(?,?))),?)

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 26ms
memory: 3548kb

input:

max(max(?,?),max(max(max(?,?),max(?,?)),max(?,max(?,?))))

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 35ms
memory: 3516kb

input:

min(max(min(?,?),?),max(min(?,max(min(max(?,?),?),?)),?))

output:

7

result:

ok single line: '7'

Test #11:

score: 0
Accepted
time: 20ms
memory: 3500kb

input:

max(?,min(max(?,min(?,?)),max(max(?,?),min(?,max(?,?)))))

output:

7

result:

ok single line: '7'

Test #12:

score: 0
Accepted
time: 29ms
memory: 3500kb

input:

min(min(max(?,?),?),max(max(?,min(max(?,?),?)),max(?,?)))

output:

7

result:

ok single line: '7'

Test #13:

score: 0
Accepted
time: 27ms
memory: 3472kb

input:

min(min(min(?,?),min(?,max(?,?))),min(?,min(?,min(?,?))))

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 32ms
memory: 3436kb

input:

min(max(max(?,?),max(?,max(max(?,?),max(?,?)))),max(?,?))

output:

7

result:

ok single line: '7'

Test #15:

score: 0
Accepted
time: 30ms
memory: 3440kb

input:

max(min(?,?),min(max(min(?,?),min(?,max(?,min(?,?)))),?))

output:

7

result:

ok single line: '7'

Test #16:

score: 0
Accepted
time: 41ms
memory: 3496kb

input:

min(?,min(?,max(max(max(min(?,min(min(?,?),?)),?),?),?)))

output:

7

result:

ok single line: '7'

Test #17:

score: 0
Accepted
time: 31ms
memory: 3500kb

input:

min(?,min(?,max(?,max(min(min(min(?,min(?,?)),?),?),?))))

output:

7

result:

ok single line: '7'

Test #18:

score: 0
Accepted
time: 43ms
memory: 3564kb

input:

min(?,min(min(min(?,min(?,min(?,min(min(?,?),?)))),?),?))

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 46ms
memory: 3456kb

input:

max(max(max(?,max(?,max(?,max(?,max(max(?,?),?))))),?),?)

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 60ms
memory: 3432kb

input:

min(max(?,min(max(min(max(min(?,max(?,?)),?),?),?),?)),?)

output:

8

result:

ok single line: '8'

Test #21:

score: 0
Accepted
time: 30ms
memory: 3564kb

input:

min(min(?,?),min(min(min(?,?),min(min(?,min(?,?)),?)),?))

output:

1

result:

ok single line: '1'

Test #22:

score: 0
Accepted
time: 30ms
memory: 3436kb

input:

max(max(max(?,?),max(max(?,?),?)),max(max(?,?),max(?,?)))

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 24ms
memory: 3500kb

input:

min(max(?,min(max(?,?),?)),min(?,min(?,min(?,max(?,?)))))

output:

5

result:

ok single line: '5'

Test #24:

score: 0
Accepted
time: 34ms
memory: 3508kb

input:

min(?,max(min(min(max(?,?),?),max(?,?)),min(min(?,?),?)))

output:

6

result:

ok single line: '6'

Test #25:

score: 0
Accepted
time: 4ms
memory: 3436kb

input:

min(min(min(?,?),max(?,?)),min(min(?,?),min(?,?)))

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 4ms
memory: 3512kb

input:

min(min(min(?,?),min(?,?)),min(min(?,?),min(?,?)))

output:

1

result:

ok single line: '1'

Test #27:

score: 0
Accepted
time: 4ms
memory: 3500kb

input:

max(min(max(?,?),max(?,?)),min(max(?,?),max(?,?)))

output:

4

result:

ok single line: '4'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

max(?,?)

output:

1

result:

ok single line: '1'

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #29:

score: 0
Time Limit Exceeded

input:

min(max(min(?,max(?,max(?,?))),min(min(?,min(?,?)),?)),min(max(?,max(?,?)),min(min(?,?),min(min(?,?),?))))

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #57:

score: 0
Runtime Error

input:

min(?,min(?,min(min(min(min(?,min(min(?,min(?,min(?,min(min(?,min(?,min(min(?,min(min(?,min(?,min(?,min(min(?,min(min(?,min(min(?,min(?,min(?,min(min(?,min(min(?,min(min(min(min(?,min(min(min(min(min(?,min(min(?,min(min(?,min(?,min(?,min(?,min(min(?,min(?,min(?,min(?,min(min(?,min(?,min(?,min(min(mi...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%