QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#141003 | #4400. Homework | mohos_risitas | 10 | 60ms | 3564kb | C++14 | 2.6kb | 2023-08-17 05:26:56 | 2023-08-17 05:26:57 |
Judging History
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%