QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #56904 | #2510. Make Numbers | Sa3tElSefr# | AC ✓ | 3ms | 3748kb | C++20 | 5.1kb | 2022-10-21 20:39:15 | 2022-10-21 20:39:17 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define ll long long
#define ld double
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
vector<int> curV, a(4);
vector<vector<int> > reached;
void generateAll(int idx) {
if(idx == 4) {
if((int) curV.size() > 1) {
reached.push_back(curV);
}
return;
}
curV.push_back(a[idx]);
generateAll(idx + 1);
curV.pop_back();
curV.back() *= 10;
curV.back() += a[idx];
generateAll(idx + 1);
curV.back() /= 10;
}
bool seen[N];
vector<char> ch;
int get() {
if((int) ch.size() == 1) {
if(ch[0] == '+') return curV[0] + curV[1];
else if(ch[0] == '-') return curV[0] - curV[1];
else return curV[0] * curV[1];
}
else if((int) ch.size() == 2){
if(ch[1] == '+') {
if(ch[0] == '+') return curV[0] + curV[1] + curV[2];
else if(ch[0] == '-') return curV[0] - curV[1] + curV[2];
else return curV[0] * curV[1] + curV[2];
}
else if(ch[1] == '-') {
if(ch[0] == '+') return curV[0] + curV[1] - curV[2];
else if(ch[0] == '-') return curV[0] - curV[1] - curV[2];
else return curV[0] * curV[1] - curV[2];
}
else {
if(ch[0] == '+') return curV[0] + curV[1] * curV[2];
else if(ch[0] == '-') return curV[0] - curV[1] * curV[2];
else return curV[0] * curV[1] * curV[2];
}
}
else {
if(ch.back() == '+') {
if(ch[1] == '+') {
if(ch[0] == '+') return curV[0] + curV[1] + curV[2] + curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] + curV[2] + curV.back();
else return curV[0] * curV[1] + curV[2] + curV.back();
}
else if(ch[1] == '-') {
if(ch[0] == '+') return curV[0] + curV[1] - curV[2] + curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] - curV[2] + curV.back();
else return curV[0] * curV[1] - curV[2] + curV.back();
}
else {
if(ch[0] == '+') return curV[0] + curV[1] * curV[2] + curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] * curV[2] + curV.back();
else return curV[0] * curV[1] * curV[2] + curV.back();
}
}
else if(ch.back() == '-') {
if(ch[1] == '+') {
if(ch[0] == '+') return curV[0] + curV[1] + curV[2] - curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] + curV[2] - curV.back();
else return curV[0] * curV[1] + curV[2] - curV.back();
}
else if(ch[1] == '-') {
if(ch[0] == '+') return curV[0] + curV[1] - curV[2] - curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] - curV[2] - curV.back();
else return curV[0] * curV[1] - curV[2] - curV.back();
}
else {
if(ch[0] == '+') return curV[0] + curV[1] * curV[2] - curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] * curV[2] - curV.back();
else return curV[0] * curV[1] * curV[2] - curV.back();
}
}
else {
if(ch[1] == '+') {
if(ch[0] == '+') return curV[0] + curV[1] + curV[2] * curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] + curV[2] * curV.back();
else return curV[0] * curV[1] + curV[2] * curV.back();
}
else if(ch[1] == '-') {
if(ch[0] == '+') return curV[0] + curV[1] - curV[2] * curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] - curV[2] * curV.back();
else return curV[0] * curV[1] - curV[2] * curV.back();
}
else {
if(ch[0] == '+') return curV[0] + curV[1] * curV[2] * curV.back();
else if(ch[0] == '-') return curV[0] - curV[1] * curV[2] * curV.back();
else return curV[0] * curV[1] * curV[2] * curV.back();
}
}
}
assert(0);
}
void generate(int idx) {
if(idx == (int) curV.size()) {
int cur = get();
if(cur >= 0) seen[cur] = 1;
return;
}
ch.push_back('+');
generate(idx + 1);
ch.pop_back();
ch.push_back('-');
generate(idx + 1);
ch.pop_back();
ch.push_back('*');
generate(idx + 1);
ch.pop_back();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for(int i = 0; i < 4; i++) cin >> a[i];
sort(a.begin(), a.end());
do {
curV = {a[0]};
generateAll(1);
}while(next_permutation(a.begin(), a.end()));
for(auto i: reached) {
curV = i;
generate(1);
}
int c = 0;
for(int i = 0; i < N; i++) {
c += seen[i];
}
cout << c;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3744kb
input:
1 1 1 1
output:
15
result:
ok single line: '15'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 1 1 1
output:
15
result:
ok single line: '15'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
1 1 2 1
output:
32
result:
ok single line: '32'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
1 2 4 8
output:
178
result:
ok single line: '178'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3572kb
input:
1 3 3 8
output:
107
result:
ok single line: '107'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
1 1 2 1
output:
32
result:
ok single line: '32'
Test #7:
score: 0
Accepted
time: 3ms
memory: 3584kb
input:
2 2 4 4
output:
58
result:
ok single line: '58'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
2 3 4 5
output:
183
result:
ok single line: '183'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3596kb
input:
2 3 5 7
output:
191
result:
ok single line: '191'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
2 4 6 8
output:
172
result:
ok single line: '172'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
2 5 5 5
output:
54
result:
ok single line: '54'
Test #12:
score: 0
Accepted
time: 3ms
memory: 3748kb
input:
2 8 6 4
output:
172
result:
ok single line: '172'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
3 3 3 3
output:
22
result:
ok single line: '22'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
5 3 2 7
output:
191
result:
ok single line: '191'
Test #15:
score: 0
Accepted
time: 3ms
memory: 3536kb
input:
5 7 8 9
output:
217
result:
ok single line: '217'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3568kb
input:
9 9 9 9
output:
20
result:
ok single line: '20'