QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #180148 | #7128. Huge products | ucup-team004# | WA | 21ms | 8560kb | C++20 | 4.4kb | 2023-09-15 16:08:53 | 2023-09-15 16:08:53 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 1000000007;
const std::vector<std::vector<std::pair<int, int>>> d {
{{5, -1}, {6, 2}, {8, -1}, {9, -1}, {10, 1}},
{{5, -1}, {6, -4}, {8, 1}, {9, 2}, {10, 1}},
{{5, -2}, {6, -2}, {9, 1}, {10, 2}},
{{5, -3}, {8, -1}, {10, 3}},
{{4, -1}, {5, 1}, {8, 1}, {10, -1}},
{{4, -1}, {6, 2}, {9, -1}},
{{4, -1}, {6, -4}, {8, 2}, {9, 2}},
{{4, -1}, {5, -1}, {6, -2}, {8, 1}, {9, 1}, {10, 1}},
{{4, -1}, {5, -2}, {10, 2}},
{{4, -2}, {6, -2}, {8, 2}, {9, 1}},
{{4, -2}, {5, -1}, {8, 1}, {10, 1}},
{{4, -3}, {8, 2}},
{{3, -1}, {5, 1}, {6, 1}, {10, -1}},
{{3, -1}, {4, 1}, {6, 1}, {8, -1}},
{{3, -1}, {5, -2}, {6, 1}, {8, -1}, {10, 2}},
{{3, -1}, {4, -1}, {5, -1}, {6, 1}, {10, 1}},
{{3, -1}, {4, -2}, {6, 1}, {8, 1}},
{{3, -2}, {5, -1}, {6, 2}, {8, -1}, {10, 1}},
{{3, -2}, {4, -1}, {6, 2}},
{{3, -3}, {6, 3}, {8, -1}},
{{2, -1}, {5, 2}, {8, 1}, {10, -2}},
{{2, -1}, {3, 1}, {6, 1}, {9, -1}},
{{2, -1}, {5, 1}, {6, 2}, {9, -1}, {10, -1}},
{{2, -1}, {6, 4}, {8, -1}, {9, -2}},
{{2, -1}, {6, -2}, {8, 1}, {9, 1}},
{{2, -1}, {5, -1}, {10, 1}},
{{2, -1}, {3, -1}, {6, 1}},
{{2, -1}, {3, -1}, {5, 1}, {6, -1}, {8, 1}, {9, 1}, {10, -1}},
{{2, -2}, {6, 2}, {9, -1}},
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 a[11];
for (int i = 1; i <= 10; i++) {
std::cin >> a[i];
}
a[1] = 0;
if (a[2]) {
a[2] += a[4] * 2;
a[4] = 0;
}
if (a[3]) {
a[3] += a[9] * 2;
a[9] = 0;
}
if (a[2] >= 2) {
a[2] += a[8] * 3;
a[8] = 0;
}
std::map<std::vector<int>, int> f;
f[std::vector<int>(21)] = 1;
for (auto u : d) {
auto g = f;
for (auto [x, y] : g) {
auto nx = x;
for (auto [a, b] : u) {
nx[a] = std::max(nx[a], b);
nx[a + 10] = std::min(nx[a + 10], b);
}
f[nx] -= y;
}
}
// if (a[2] < 100) {
// using i128 = __int128;
// // std::set<i128> s;
// std::map<i128, std::vector<int>> s;
// std::vector<int> cnt(11);
// std::vector<std::vector<int>> d;
// auto dfs = [&](auto self, int x, i128 v) {
// if (x == 11) {
// if (!s.count(v)) {
// s[v] = cnt;
// } else {
// std::vector<int> x(11);
// for (int i = 1; i <= 10; i++) {
// x[i] = s[v][i] - cnt[i];
// }
// bool add = true;
// for (auto u : d) {
// bool ok = false;
// for (int i = 1; i <= 10; i++) {
// if (x[i] > 0 && u[i] < 0 || x[i] < 0 && u[i] > 0 || std::abs(x[i]) < std::abs(u[i])) {
// ok = true;
// }
// }
// if (!ok) {
// add = false;
// }
// }
// if (add) {
// d.push_back(x);
// std::cout << "{";
// for (int i = 1; i <= 10; i++) {
// if (x[i]) {
// std::cout << "{" << i << ", " << x[i] << "}, ";
// }
// }
// std::cout << "},\n";
// }
// }
// return;
// }
// for (int i = 0; i <= a[x]; i++) {
// if (i) {
// v *= x;
// }
// cnt[x] = i;
// self(self, x + 1, v);
// }
// };
// dfs(dfs, 1, 1);
// std::cout << s.size() << "\n";
// }
int ans = 0;
for (auto [x, y] : f) {
int res = 1;
for (int i = 1; i <= 10; i++) {
res = 1LL * res * std::max(0LL, a[i] + 1 - x[i] + x[i + 10]) % P;
}
ans = (ans + 1LL * res * (y + P)) % P;
}
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 21ms
memory: 8280kb
input:
0 1 0 1 0 0 0 1 0 0
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 20ms
memory: 8300kb
input:
0 1000000000 100000000 0 0 0 0 0 0 0
output:
400000001
result:
ok 1 number(s): "400000001"
Test #3:
score: 0
Accepted
time: 20ms
memory: 8236kb
input:
5 1 1 5 0 0 3 4 4 0
output:
960
result:
ok 1 number(s): "960"
Test #4:
score: 0
Accepted
time: 16ms
memory: 8232kb
input:
0 3 4 0 1 0 2 2 0 2
output:
630
result:
ok 1 number(s): "630"
Test #5:
score: 0
Accepted
time: 15ms
memory: 8228kb
input:
2 1 0 0 0 1 3 0 0 0
output:
16
result:
ok 1 number(s): "16"
Test #6:
score: 0
Accepted
time: 20ms
memory: 8192kb
input:
2 1 0 0 0 0 0 0 0 3
output:
8
result:
ok 1 number(s): "8"
Test #7:
score: 0
Accepted
time: 20ms
memory: 8232kb
input:
0 2 2 0 2 0 5 5 3 0
output:
2916
result:
ok 1 number(s): "2916"
Test #8:
score: 0
Accepted
time: 20ms
memory: 8308kb
input:
1 0 1 2 1 4 3 0 0 1
output:
400
result:
ok 1 number(s): "400"
Test #9:
score: 0
Accepted
time: 20ms
memory: 8236kb
input:
3 2 2 1 0 4 1 3 4 0
output:
500
result:
ok 1 number(s): "500"
Test #10:
score: 0
Accepted
time: 16ms
memory: 8228kb
input:
1 0 2 2 0 3 3 0 0 0
output:
128
result:
ok 1 number(s): "128"
Test #11:
score: 0
Accepted
time: 20ms
memory: 8336kb
input:
5 3 0 2 0 1 1 0 3 0
output:
128
result:
ok 1 number(s): "128"
Test #12:
score: 0
Accepted
time: 20ms
memory: 8300kb
input:
0 2 1 2 0 2 1 0 0 1
output:
120
result:
ok 1 number(s): "120"
Test #13:
score: 0
Accepted
time: 20ms
memory: 8540kb
input:
4 0 0 2 0 1 3 0 0 0
output:
24
result:
ok 1 number(s): "24"
Test #14:
score: 0
Accepted
time: 20ms
memory: 8192kb
input:
2 2 1 2 0 2 3 0 3 0
output:
336
result:
ok 1 number(s): "336"
Test #15:
score: 0
Accepted
time: 16ms
memory: 8492kb
input:
4 0 1 0 4 0 2 1 0 0
output:
60
result:
ok 1 number(s): "60"
Test #16:
score: 0
Accepted
time: 14ms
memory: 8528kb
input:
1 0 1 2 1 0 5 0 4 0
output:
360
result:
ok 1 number(s): "360"
Test #17:
score: 0
Accepted
time: 20ms
memory: 8340kb
input:
3 1 0 1 0 0 5 0 5 2
output:
432
result:
ok 1 number(s): "432"
Test #18:
score: 0
Accepted
time: 20ms
memory: 8504kb
input:
1 1 0 4 0 3 0 0 5 0
output:
160
result:
ok 1 number(s): "160"
Test #19:
score: 0
Accepted
time: 20ms
memory: 8284kb
input:
5 1 0 0 3 5 2 1 1 0
output:
528
result:
ok 1 number(s): "528"
Test #20:
score: 0
Accepted
time: 16ms
memory: 8232kb
input:
2 0 0 0 0 0 1 0 2 0
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: 0
Accepted
time: 20ms
memory: 8308kb
input:
4 2 0 1 0 0 4 3 0 0
output:
70
result:
ok 1 number(s): "70"
Test #22:
score: 0
Accepted
time: 20ms
memory: 8544kb
input:
0 0 0 2 0 4 2 0 0 0
output:
45
result:
ok 1 number(s): "45"
Test #23:
score: 0
Accepted
time: 16ms
memory: 8304kb
input:
4 2 1 5 2 0 1 0 2 1
output:
648
result:
ok 1 number(s): "648"
Test #24:
score: 0
Accepted
time: 21ms
memory: 8296kb
input:
3 0 4 0 3 3 1 4 0 5
output:
2200
result:
ok 1 number(s): "2200"
Test #25:
score: 0
Accepted
time: 20ms
memory: 8528kb
input:
1 2 0 1 0 0 2 0 1 0
output:
30
result:
ok 1 number(s): "30"
Test #26:
score: 0
Accepted
time: 17ms
memory: 8528kb
input:
3 0 1 1 1 0 2 0 5 0
output:
144
result:
ok 1 number(s): "144"
Test #27:
score: 0
Accepted
time: 20ms
memory: 8228kb
input:
5 0 2 1 4 4 0 0 0 3
output:
312
result:
ok 1 number(s): "312"
Test #28:
score: 0
Accepted
time: 20ms
memory: 8304kb
input:
0 1 5 2 0 2 3 0 3 0
output:
424
result:
ok 1 number(s): "424"
Test #29:
score: 0
Accepted
time: 20ms
memory: 8240kb
input:
2 1 1 3 0 0 4 0 0 0
output:
80
result:
ok 1 number(s): "80"
Test #30:
score: 0
Accepted
time: 20ms
memory: 8464kb
input:
4 1 3 0 0 5 3 0 5 0
output:
412
result:
ok 1 number(s): "412"
Test #31:
score: 0
Accepted
time: 20ms
memory: 8296kb
input:
0 3 0 0 0 2 2 0 0 4
output:
180
result:
ok 1 number(s): "180"
Test #32:
score: 0
Accepted
time: 16ms
memory: 8272kb
input:
4 1 1 4 0 0 4 0 0 5
output:
600
result:
ok 1 number(s): "600"
Test #33:
score: 0
Accepted
time: 13ms
memory: 8296kb
input:
5 2 1 2 5 0 5 1 0 4
output:
1440
result:
ok 1 number(s): "1440"
Test #34:
score: 0
Accepted
time: 16ms
memory: 8232kb
input:
3 1 0 1 3 1 2 4 1 2
output:
1224
result:
ok 1 number(s): "1224"
Test #35:
score: 0
Accepted
time: 19ms
memory: 8188kb
input:
1 0 1 2 0 0 1 3 3 0
output:
192
result:
ok 1 number(s): "192"
Test #36:
score: 0
Accepted
time: 12ms
memory: 8192kb
input:
3 2 0 2 0 2 4 0 0 0
output:
105
result:
ok 1 number(s): "105"
Test #37:
score: 0
Accepted
time: 12ms
memory: 8256kb
input:
0 0 0 1 0 1 1 0 3 0
output:
32
result:
ok 1 number(s): "32"
Test #38:
score: 0
Accepted
time: 20ms
memory: 8560kb
input:
2 2 4 2 0 0 4 0 0 4
output:
875
result:
ok 1 number(s): "875"
Test #39:
score: 0
Accepted
time: 16ms
memory: 8464kb
input:
0 1 3 2 2 0 3 0 0 5
output:
928
result:
ok 1 number(s): "928"
Test #40:
score: 0
Accepted
time: 20ms
memory: 8228kb
input:
4 1 0 2 1 4 5 0 1 2
output:
1236
result:
ok 1 number(s): "1236"
Test #41:
score: 0
Accepted
time: 15ms
memory: 8224kb
input:
1 1 1 2 0 0 5 3 0 0
output:
180
result:
ok 1 number(s): "180"
Test #42:
score: 0
Accepted
time: 20ms
memory: 8540kb
input:
5 3 1 1 0 0 0 0 2 0
output:
36
result:
ok 1 number(s): "36"
Test #43:
score: 0
Accepted
time: 19ms
memory: 8468kb
input:
5 1 0 1 0 1 4 1 3 0
output:
280
result:
ok 1 number(s): "280"
Test #44:
score: 0
Accepted
time: 15ms
memory: 8304kb
input:
3 2 0 2 2 3 1 0 0 0
output:
168
result:
ok 1 number(s): "168"
Test #45:
score: 0
Accepted
time: 20ms
memory: 8300kb
input:
5 1 4 4 0 1 2 1 1 0
output:
330
result:
ok 1 number(s): "330"
Test #46:
score: 0
Accepted
time: 20ms
memory: 8260kb
input:
0 0 1 0 3 0 0 0 0 0
output:
8
result:
ok 1 number(s): "8"
Test #47:
score: 0
Accepted
time: 21ms
memory: 8308kb
input:
2 2 0 0 0 0 3 0 0 5
output:
72
result:
ok 1 number(s): "72"
Test #48:
score: 0
Accepted
time: 20ms
memory: 8540kb
input:
4 0 5 1 0 0 4 0 0 0
output:
60
result:
ok 1 number(s): "60"
Test #49:
score: 0
Accepted
time: 20ms
memory: 8300kb
input:
0 2 1 2 3 0 1 3 0 0
output:
256
result:
ok 1 number(s): "256"
Test #50:
score: 0
Accepted
time: 20ms
memory: 8524kb
input:
1 0 1 2 0 0 2 0 0 2
output:
54
result:
ok 1 number(s): "54"
Test #51:
score: 0
Accepted
time: 16ms
memory: 8228kb
input:
3 3 1 0 0 5 5 4 5 0
output:
1962
result:
ok 1 number(s): "1962"
Test #52:
score: 0
Accepted
time: 16ms
memory: 8236kb
input:
5 0 0 1 0 0 5 0 5 5
output:
432
result:
ok 1 number(s): "432"
Test #53:
score: 0
Accepted
time: 19ms
memory: 8304kb
input:
98085918 0 1 0 0 355431774 584158301 250629166 0 0
output:
269418441
result:
ok 1 number(s): "269418441"
Test #54:
score: 0
Accepted
time: 20ms
memory: 8236kb
input:
940350702 0 559496198 264431242 219676070 193178866 415296654 0 0 0
output:
777329375
result:
ok 1 number(s): "777329375"
Test #55:
score: 0
Accepted
time: 21ms
memory: 8240kb
input:
151211705 0 508398953 673816570 996622761 0 394401161 898597245 601916151 532212287
output:
129253427
result:
ok 1 number(s): "129253427"
Test #56:
score: 0
Accepted
time: 16ms
memory: 8540kb
input:
993476489 0 1 415966121 0 110005939 770310760 156975250 215145588 454036580
output:
450367235
result:
ok 1 number(s): "450367235"
Test #57:
score: 0
Accepted
time: 20ms
memory: 8300kb
input:
540773980 0 1 1 0 0 886952630 0 128107739 634137061
output:
34938943
result:
ok 1 number(s): "34938943"
Test #58:
score: 0
Accepted
time: 19ms
memory: 8296kb
input:
46602274 0 240009090 2 0 0 860286896 310662918 0 134587013
output:
691016451
result:
ok 1 number(s): "691016451"
Test #59:
score: 0
Accepted
time: 11ms
memory: 8276kb
input:
593899767 0 0 2 712113829 0 182709596 0 101274901 926089482
output:
554643997
result:
ok 1 number(s): "554643997"
Test #60:
score: 0
Accepted
time: 17ms
memory: 8276kb
input:
804760770 0 22716474 1 481752522 726470661 454434913 0 717591949 3006517
output:
80500674
result:
ok 1 number(s): "80500674"
Test #61:
score: 0
Accepted
time: 19ms
memory: 8240kb
input:
941992845 0 266586520 0 74555750 0 286769422 0 0 845530906
output:
819253021
result:
ok 1 number(s): "819253021"
Test #62:
score: 0
Accepted
time: 20ms
memory: 8236kb
input:
527510235 0 0 610908246 0 982199250 9162410 0 0 332105033
output:
109271144
result:
ok 1 number(s): "109271144"
Test #63:
score: 0
Accepted
time: 21ms
memory: 8464kb
input:
369775018 0 1 1 562248581 464178648 666324577 501068018 123607501 0
output:
652349849
result:
ok 1 number(s): "652349849"
Test #64:
score: 0
Accepted
time: 20ms
memory: 8232kb
input:
580636022 0 0 213996894 891827629 635208715 624484223 0 251546458 200666932
output:
383166838
result:
ok 1 number(s): "383166838"
Test #65:
score: 0
Accepted
time: 20ms
memory: 8240kb
input:
422900805 0 780509514 0 189663564 547565999 807039403 886694898 0 753800295
output:
980770301
result:
ok 1 number(s): "980770301"
Test #66:
score: 0
Accepted
time: 19ms
memory: 8300kb
input:
338794516 0 1 0 0 487499501 501392480 0 0 754464806
output:
890042066
result:
ok 1 number(s): "890042066"
Test #67:
score: 0
Accepted
time: 16ms
memory: 8520kb
input:
476026592 0 268249605 600545840 0 413749764 950811398 695863642 0 0
output:
962749562
result:
ok 1 number(s): "962749562"
Test #68:
score: 0
Accepted
time: 16ms
memory: 8188kb
input:
391920303 0 0 0 673494679 0 662543537 0 187046265 459025527
output:
355434275
result:
ok 1 number(s): "355434275"
Test #69:
score: 0
Accepted
time: 20ms
memory: 8184kb
input:
234185086 0 0 631783930 0 0 911337310 684517975 0 955560704
output:
266807088
result:
ok 1 number(s): "266807088"
Test #70:
score: 0
Accepted
time: 20ms
memory: 8232kb
input:
76449869 0 999859744 2 15279733 528727302 235669374 0 0 0
output:
579662066
result:
ok 1 number(s): "579662066"
Test #71:
score: 0
Accepted
time: 16ms
memory: 8300kb
input:
287310873 0 0 866276358 313115669 0 343448370 0 0 0
output:
639977759
result:
ok 1 number(s): "639977759"
Test #72:
score: 0
Accepted
time: 20ms
memory: 8492kb
input:
980596438 0 0 1 0 0 160294960 0 710968086 0
output:
960314807
result:
ok 1 number(s): "960314807"
Test #73:
score: 0
Accepted
time: 20ms
memory: 8188kb
input:
822861221 0 615365072 0 0 0 470787623 0 535735203 0
output:
678323069
result:
ok 1 number(s): "678323069"
Test #74:
score: 0
Accepted
time: 16ms
memory: 8232kb
input:
370158712 0 154202410 0 0 0 383144907 0 0 0
output:
162400112
result:
ok 1 number(s): "162400112"
Test #75:
score: 0
Accepted
time: 20ms
memory: 8188kb
input:
875987008 0 0 0 558669042 0 336971388 700858771 0 0
output:
389180595
result:
ok 1 number(s): "389180595"
Test #76:
score: 0
Accepted
time: 19ms
memory: 8232kb
input:
423284499 0 1 2 336650589 940954700 690868827 0 0 0
output:
217840333
result:
ok 1 number(s): "217840333"
Test #77:
score: -100
Wrong Answer
time: 16ms
memory: 8240kb
input:
634145502 0 0 0 0 591830686 793089737 771001838 176334283 0
output:
756746481
result:
wrong answer 1st numbers differ - expected: '123815246', found: '756746481'