QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456419 | #7131. Random points | propane | AC ✓ | 322ms | 4052kb | C++20 | 3.2kb | 2024-06-27 21:56:14 | 2024-06-27 21:56:14 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 2005, mod = 1e9 + 7;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
}
int sub(int a, int b){
a -= b;
if (a < 0) a += mod;
return a;
}
int mul(int a, int b){
return 1LL * a * b % mod;
}
int pow2[maxn];
struct Point{
LL x, y;
bool operator==(const Point &t) const {
return x == t.x and y == t.y;
}
Point operator-(const Point &t) const {
return {x - t.x, y - t.y};
}
LL operator*(const Point &t) const {
return x * t.x + y * t.y;
}
LL operator^(const Point &t) const {
return x * t.y - y * t.x;
}
int quad() const {
if (y < 0) return 1;
if (y > 0) return 4;
if (x > 0) return 2;
if (x < 0) return 5;
return 3;
}
bool operator<(const Point &t) const {
int q1 = quad(), q2 = t.quad();
if (q1 != q2) return q1 < q2;
LL cross = (*this ^ t);
if (cross != 0) return cross > 0;
return (*this) * (*this) < t * t;
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
pow2[0] = 1;
for(int i = 1; i < maxn; i++){
pow2[i] = mul(pow2[i - 1], 2);
}
int n;
cin >> n;
vector<Point> p(n);
map<Point, int> mp;
for(int i = 0; i < n; i++){
cin >> p[i].x >> p[i].y;
mp[p[i]] += 1;
}
int ans = 0;
// 枚举每个点,计算其出现在凸包上的方案数
// 对于剩下的点极角排序后如果选择的其余点都在一个半平面,则该点在凸包上.
// 否则肯定被包含
// 枚举点集的方法,枚举极角序最小的点是哪个,然后找到所有与其夹角不超过pi的点
// 边界问题,极角序可能相同,一起枚举可以避免双指针转圈转回去
for(auto &[u, cnt] : mp){
vector<Point> q;
q.reserve(p.size());
for(auto pt : p){
if (pt != u){
q.push_back(pt - u);
}
}
sort(q.begin(), q.end());
auto check1 = [&](int x, int y){
LL t = q[x] ^ q[y];
if (t > 0) return true;
if (t < 0) return false;
return (q[x] * q[y]) > 0;
};
auto check2 = [&](int x, int y){
LL t = q[x] ^ q[y];
LL s = q[x] * q[y];
return t == 0 and s > 0;
};
const int m = q.size();
q.resize(2 * m);
for(int i = 0; i < m; i++) q[i + m] = q[i];
// 空集也是可以的
int sum = 1;
for(int i = 0, j = 0, k = 0; i < m; i = j){
while(j < m + i and check2(i, j)) j++;
k = max(k, j);
while(k < m + i and check1(i, k)) k++;
int c1 = j - i;
int c2 = k - j;
add(sum, mul(sub(pow2[c1], 1), pow2[c2]));
}
add(ans, mul(sub(pow2[cnt], 1), sum));
}
cout << ans << '\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
3 0 0 0 1 1 0
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 0 0 0 1 0 2
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
20 3 3 1 0 0 2 2 2 2 4 4 3 0 0 1 4 0 1 4 2 3 4 1 0 3 1 4 4 3 1 1 3 4 1 1 4 3 0 3 1
output:
5996938
result:
ok 1 number(s): "5996938"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
20 3 1 2 2 3 3 3 3 3 4 1 0 4 0 2 1 4 2 0 2 2 3 4 2 4 0 4 0 4 1 0 3 3 3 3 4 0 4 2 1
output:
5252571
result:
ok 1 number(s): "5252571"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
20 1 2 0 1 1 2 1 4 3 3 0 0 0 4 1 3 1 2 0 2 1 0 0 2 0 2 1 0 1 4 2 4 2 0 3 1 1 1 0 2
output:
5321297
result:
ok 1 number(s): "5321297"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
20 0 0 2 0 3 3 0 1 1 4 0 3 0 0 4 0 4 4 1 3 1 1 3 3 2 3 4 1 4 4 3 1 1 4 0 4 1 3 4 3
output:
4876981
result:
ok 1 number(s): "4876981"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
20 1 1 0 3 0 1 0 1 2 2 3 1 0 3 3 2 4 1 2 2 4 3 0 1 3 0 3 1 0 2 3 4 4 1 3 0 4 3 0 0
output:
5073888
result:
ok 1 number(s): "5073888"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
20 3 4 4 0 4 3 3 2 3 3 3 0 1 4 3 1 0 4 2 4 3 4 2 0 0 4 0 3 4 4 0 1 2 0 1 1 3 4 1 1
output:
5516468
result:
ok 1 number(s): "5516468"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
20 3 2 4 4 0 4 4 4 3 3 4 3 3 2 4 3 4 0 1 4 3 0 4 3 1 0 3 4 1 2 1 4 4 3 1 2 1 0 2 2
output:
4561298
result:
ok 1 number(s): "4561298"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
20 0 1 2 2 1 2 2 0 1 2 3 0 4 2 2 1 1 0 2 0 2 2 2 4 2 2 1 0 3 1 3 1 4 4 3 0 2 1 1 3
output:
5273582
result:
ok 1 number(s): "5273582"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
20 0 4 4 1 4 4 2 1 3 3 2 0 4 1 3 2 3 2 2 0 2 4 0 0 2 1 0 1 0 0 2 3 2 2 2 0 2 3 4 4
output:
4934815
result:
ok 1 number(s): "4934815"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
20 0 1 2 4 3 2 1 3 4 3 4 0 4 4 3 4 4 3 0 4 0 0 4 2 4 3 2 1 4 4 0 0 2 1 2 4 0 1 0 0
output:
5033049
result:
ok 1 number(s): "5033049"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
20 19 19 1 1 4 5 10 20 3 4 11 19 20 15 6 0 9 17 17 16 8 18 18 16 0 16 15 6 8 10 1 7 11 18 5 2 10 19 4 13
output:
6215411
result:
ok 1 number(s): "6215411"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
20 5 2 3 8 18 13 20 9 11 18 7 4 3 6 8 16 8 0 18 16 0 14 7 8 9 3 12 1 17 8 17 20 7 19 5 14 1 11 6 0
output:
7150834
result:
ok 1 number(s): "7150834"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
20 5 7 1 18 19 13 10 3 18 12 17 1 20 14 9 3 7 9 6 7 16 1 12 8 14 15 10 12 13 11 3 17 9 0 12 1 14 16 2 11
output:
5655954
result:
ok 1 number(s): "5655954"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
20 5 4 10 17 4 17 16 0 5 14 17 7 7 5 19 19 2 1 3 20 15 5 17 5 19 6 11 2 9 1 5 9 19 5 4 9 5 13 8 15
output:
5525854
result:
ok 1 number(s): "5525854"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
20 4 4 16 7 2 0 6 10 9 11 9 5 20 9 20 5 1 10 3 3 7 13 18 1 7 1 0 13 18 20 20 5 12 19 12 9 18 13 18 1
output:
5996819
result:
ok 1 number(s): "5996819"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
20 12 9 4 14 16 17 12 3 16 5 18 7 7 0 9 0 13 18 17 12 15 18 2 5 12 13 6 4 15 2 10 19 1 7 12 16 9 10 3 13
output:
7358820
result:
ok 1 number(s): "7358820"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
20 12 9 6 9 9 0 19 1 3 3 11 4 20 12 10 7 12 10 17 3 6 18 7 18 18 4 20 19 11 17 12 19 10 0 11 7 18 3 8 20
output:
6109530
result:
ok 1 number(s): "6109530"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
20 15 14 7 19 20 4 8 11 6 13 3 10 7 3 12 7 11 19 18 16 6 1 8 15 2 16 17 9 20 20 2 12 20 9 19 15 10 7 1 3
output:
5983987
result:
ok 1 number(s): "5983987"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
20 2 7 17 5 17 8 18 4 5 19 12 8 7 11 0 10 6 3 14 16 1 9 9 19 7 11 15 8 16 14 13 8 9 7 19 6 5 0 7 18
output:
6056527
result:
ok 1 number(s): "6056527"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
20 4 4 8 15 11 12 13 8 4 7 19 10 15 13 5 11 12 2 8 9 14 6 10 11 1 0 18 9 2 11 10 1 11 15 20 4 0 20 18 20
output:
5673043
result:
ok 1 number(s): "5673043"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
20 336405873 965255840 652652222 713068201 61495714 864495608 289278684 273789489 705069803 645861692 283828514 807458721 135671792 915838066 347383048 781174151 27017020 165786268 525637386 825246400 999273165 170356496 298705494 542641581 341157969 620048533 800792019 74468194 984766973 453177943 ...
output:
6305503
result:
ok 1 number(s): "6305503"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
20 252299584 188575412 500890006 956938247 568072747 568848227 587114620 755768888 617427087 934427639 834979913 346516263 3441700 707340534 135002005 965711294 928983573 745563964 871761848 196491818 592549325 478511618 41256982 558819978 127405696 280355780 77055590 900799165 767802897 415054489 4...
output:
7583216
result:
ok 1 number(s): "7583216"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
20 94564367 821960402 54160499 495775584 369617070 346829774 884950557 164119358 571253568 222993586 722567801 549137317 871211609 130246782 554024742 518844655 535982833 30374368 627951726 862704529 890858194 155262959 447371983 206402156 618686132 14291956 648286454 432162842 919435041 155592671 4...
output:
6113607
result:
ok 1 number(s): "6113607"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
20 305425371 45279974 533802064 444678338 171161394 419778612 887819201 646098758 483610852 511559533 610155688 383162151 444014225 626781959 678080188 71978017 364320458 315184772 974076188 528917239 189167063 463418081 894956180 222580553 478562787 84664620 219517317 553461104 407503672 117469217 ...
output:
6764925
result:
ok 1 number(s): "6764925"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
20 147690154 973632256 87072557 688548385 972705718 902792868 112026208 54449228 732404625 168721699 161307087 585783206 680380353 123317134 97102924 256515160 266287010 894962468 320200649 531566439 487475932 771573203 6103888 533726242 674875931 113568087 127184669 84824781 895572305 784378472 485...
output:
6070154
result:
ok 1 number(s): "6070154"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
20 63583865 607017245 935310342 932418431 774250042 975741707 114894853 536428627 981198398 162320354 343862266 124840748 253182969 251256091 884721882 809648523 168253562 548369091 371357819 902811858 785784801 153357252 43622668 549904640 461123658 478908044 403448241 911155751 342171740 819883946...
output:
7110644
result:
ok 1 number(s): "7110644"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
20 200815941 830336818 783548127 176288476 280827074 385127033 412730789 313375317 598588390 450886301 895013666 327461802 825985586 42758559 303744618 362781884 70220114 128146787 717482281 569024568 84093669 756479666 154770376 566083037 321000313 212844219 679711814 442519429 830240373 486793201 ...
output:
6109083
result:
ok 1 number(s): "6109083"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
20 748113433 463721807 336818619 420158523 82371397 458075872 710566725 426758497 847382163 739452248 782601553 866519345 693755494 539293736 427800064 547319027 603590448 412957191 63606742 866641059 677369830 769667496 897321866 582261434 812280750 578184176 882346458 268850398 613276296 522298675...
output:
5471625
result:
ok 1 number(s): "5471625"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
20 958974436 392074088 185056404 664028569 515319502 236057419 713435369 908737896 464772155 28018194 38785660 69140399 266558111 962199984 215419021 100452389 800524292 992734887 114763912 532853770 975678699 446418837 8469573 893407123 303561185 312120351 453577321 800214076 101344928 189207929 21...
output:
6290548
result:
ok 1 number(s): "6290548"
Test #32:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
20 839459118 250813388 210886587 446341423 734699739 162312946 524969959 813259360 258532670 119007402 923976993 893230085 550966829 448774111 741957996 712341646 706719531 570008421 787701275 362968182 522566755 949914939 38822846 811020160 966058391 438380044 477726558 572987885 123261355 68952904...
output:
5963046
result:
ok 1 number(s): "5963046"
Test #33:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
100 17 6 15 13 3 13 15 2 3 17 4 0 7 11 20 13 7 18 14 4 13 20 15 18 6 4 8 12 2 17 8 6 15 7 17 0 13 10 18 19 20 9 3 18 14 7 13 1 15 8 10 11 8 16 20 9 8 5 4 9 6 7 8 19 12 1 7 2 7 7 4 16 1 19 5 4 9 19 14 11 7 15 2 20 17 6 1 11 5 16 17 4 14 20 7 14 2 18 14 0 19 12 0 13 16 5 16 1 0 8 12 16 1 10 4 11 18 1 ...
output:
629516671
result:
ok 1 number(s): "629516671"
Test #34:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
100 10 11 17 7 2 10 20 2 10 14 5 17 12 17 17 6 8 20 5 9 14 15 20 8 10 7 11 9 4 2 9 3 15 8 15 10 9 14 15 18 2 2 14 15 10 20 9 10 10 18 14 12 15 17 11 15 13 13 3 16 11 3 10 13 2 7 2 8 15 13 8 0 9 0 12 0 14 7 20 15 8 7 2 7 1 3 18 17 18 10 10 19 4 3 0 5 8 15 19 9 11 11 10 13 17 4 5 0 2 11 12 8 6 10 10 3...
output:
772969884
result:
ok 1 number(s): "772969884"
Test #35:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 7 2 15 13 6 14 5 16 17 14 2 13 0 15 10 11 1 14 18 11 11 14 16 18 20 15 15 7 9 11 14 4 2 2 6 4 12 6 17 14 17 12 4 8 18 12 1 6 1 14 5 1 10 10 7 12 15 17 19 14 16 7 0 11 17 17 15 14 2 11 7 5 1 20 11 0 16 12 2 18 0 15 18 6 2 10 7 14 5 16 12 3 8 3 15 17 19 11 17 5 3 10 20 17 18 8 19 11 9 14 9 13 18 9...
output:
547585677
result:
ok 1 number(s): "547585677"
Test #36:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
100 8 7 16 3 2 18 14 12 20 10 3 13 0 20 12 3 6 16 18 16 16 17 9 4 16 19 5 4 11 8 7 5 2 4 14 10 7 7 6 10 17 1 16 1 14 16 18 19 3 7 9 19 17 11 6 18 16 12 14 20 8 4 6 13 8 14 10 3 14 13 2 10 18 14 11 13 17 0 5 14 14 3 0 10 8 4 3 19 4 0 4 4 2 16 8 20 4 7 18 0 16 17 0 17 2 20 9 5 7 8 9 9 10 9 0 8 9 9 15 ...
output:
145089569
result:
ok 1 number(s): "145089569"
Test #37:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
100 19 19 14 18 1 15 2 16 6 11 8 9 9 1 6 4 7 18 6 4 13 15 5 19 17 14 17 1 16 14 12 1 20 19 8 20 7 7 7 9 20 15 6 15 5 8 10 19 19 4 0 17 11 16 2 16 17 12 13 18 9 17 12 6 15 0 2 9 1 16 19 10 13 17 18 13 19 9 8 1 10 15 17 10 0 10 0 8 12 10 18 13 9 3 2 7 7 8 2 0 15 16 14 0 3 11 19 16 18 8 14 6 19 4 10 4 ...
output:
356436740
result:
ok 1 number(s): "356436740"
Test #38:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 20 6 8 16 18 19 12 8 1 11 1 18 14 3 16 18 8 20 1 10 18 1 10 9 9 6 7 16 18 2 5 2 3 20 20 14 19 3 9 9 14 7 17 8 14 7 6 7 14 14 4 1 18 9 14 0 2 7 4 16 14 0 1 4 9 18 14 14 14 10 1 15 18 7 0 9 7 15 10 4 15 11 20 17 5 17 17 5 3 3 7 7 4 3 16 1 17 8 4 16 7 16 3 0 20 2 9 15 20 11 14 19 11 4 12 20 9 19 16...
output:
210583523
result:
ok 1 number(s): "210583523"
Test #39:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
100 0 19 6 10 1 15 9 1 8 3 6 18 1 4 13 18 10 5 10 2 2 17 19 20 2 5 11 13 2 16 10 15 20 14 19 3 2 8 6 4 18 17 11 18 9 20 19 8 4 14 20 20 12 7 10 2 7 7 3 6 15 17 8 2 4 3 6 3 5 12 0 20 13 10 20 17 9 3 13 0 7 20 19 13 11 11 13 14 15 9 16 12 11 16 14 0 2 4 1 4 7 11 5 4 0 6 2 1 18 5 15 7 3 3 17 8 0 3 13 1...
output:
675593564
result:
ok 1 number(s): "675593564"
Test #40:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
100 18 2 8 17 14 3 19 1 15 7 11 10 6 6 15 11 3 2 11 7 2 19 20 9 6 18 14 11 4 0 11 16 12 16 9 17 1 4 8 0 4 10 14 11 18 12 15 4 7 20 19 4 10 0 5 3 12 2 16 4 3 14 14 13 11 9 1 9 13 18 17 0 9 4 7 0 14 12 16 8 0 11 19 0 16 17 10 20 6 15 5 13 5 20 7 12 13 13 19 17 3 14 15 4 9 5 12 0 4 8 11 20 7 11 15 0 5 ...
output:
728706610
result:
ok 1 number(s): "728706610"
Test #41:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
100 12 15 9 6 13 20 7 14 18 8 8 10 11 7 9 11 8 4 19 17 7 14 20 12 20 17 5 4 5 14 8 12 12 10 8 7 17 4 10 3 15 20 0 16 10 16 7 17 19 0 14 6 17 1 18 5 6 2 15 19 12 18 20 11 9 6 14 7 4 17 12 1 18 6 6 13 16 17 2 11 9 16 18 20 8 11 6 17 6 16 19 18 17 12 1 7 19 9 8 12 19 9 17 8 6 9 2 6 10 12 12 12 20 10 0 ...
output:
121633147
result:
ok 1 number(s): "121633147"
Test #42:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
100 12 12 12 19 15 20 8 17 7 13 13 17 11 19 3 7 13 12 4 11 3 7 18 11 0 11 5 9 9 13 13 0 11 1 1 0 15 18 7 9 18 13 0 20 1 4 4 18 6 20 2 18 2 3 12 15 8 16 1 8 16 19 0 6 4 20 7 8 2 1 13 17 11 1 13 2 20 3 4 19 7 13 15 7 6 10 5 12 13 14 15 11 13 12 4 4 13 0 6 10 8 16 10 11 1 6 6 9 7 18 1 17 19 19 13 15 12...
output:
660618691
result:
ok 1 number(s): "660618691"
Test #43:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
100 567775692 225148306 284853961 74506045 127658181 266239688 68021672 140236565 236895051 864333041 883174534 764245141 405290517 409535649 943170619 801826942 292146623 930092201 361388966 679652079 982646932 930843436 812470239 512105172 323294773 217941822 136514187 289551923 700526170 82005015...
output:
574679222
result:
ok 1 number(s): "574679222"
Test #44:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
100 20861893 452784880 795349774 765697917 287387681 75293275 243113141 318332276 321267732 728212159 776993902 430316106 885761159 802781441 829690946 925865187 738434872 790975048 97458246 209644523 393675255 876337658 711951195 368488549 364627247 404759025 332441448 154566013 91452688 471397303 ...
output:
259816346
result:
ok 1 number(s): "259816346"
Test #45:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
100 105351876 49017674 937249366 383260859 447117181 884346864 639542974 496427987 700607706 182025859 597184343 464983290 29795311 196027231 84807493 459968849 553319340 20454113 497091039 739636969 436107358 863301077 242835930 856275707 700927014 886543519 601997637 429645521 892444624 459180935 ...
output:
736099588
result:
ok 1 number(s): "736099588"
Test #46:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
100 968503496 571621540 784181666 74452729 680475609 693400451 446038223 43119917 153576607 45904977 122407491 131054255 510265953 589273023 266295113 289039802 294574880 586369669 233160319 269629414 847135682 440199080 142316886 417691793 742259488 704764502 797924898 999692321 914774924 110528079...
output:
933435086
result:
ok 1 number(s): "933435086"
Test #47:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
100 52993478 167854333 926081259 765644601 135172400 871050258 916096984 221215628 532916580 499718678 237565223 165721439 359332815 277486106 447782732 118110755 740863129 815848736 264196892 168218079 553131296 795758719 336765133 274075170 78559254 186548996 67481086 569739120 715766859 761875224...
output:
940703840
result:
ok 1 number(s): "940703840"
Test #48:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 211112388 395490908 67980850 88240251 663498120 680103845 722592233 694278631 690918190 363597796 131384592 831792405 429738040 39328117 334303060 242149001 482118669 381764291 663829684 993177817 595563400 372656722 867649869 130458548 488487948 668333490 263408347 139785919 811726086 44626148 ...
output:
553761448
result:
ok 1 number(s): "553761448"
Test #49:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 295602371 623127482 209880442 74399413 823227620 489157433 824054774 872374343 70258163 817411498 951575033 161426881 910208682 137606617 884386899 702623735 928406918 611243357 399898965 523170261 6591722 728216361 62098116 691874634 824787715 486554473 459335608 414865426 202652605 695973292 3...
output:
37494665
result:
ok 1 number(s): "37494665"
Test #50:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
100 748688574 219360275 56812743 765591284 982957120 298211020 999146243 50470053 523227064 976257907 476798181 827497846 759275543 825819701 770907227 531694688 374695166 472126204 725902829 53162706 712587338 10147072 592982852 843225304 866120189 673371675 728891797 911283298 3644540 978724217 43...
output:
973784935
result:
ok 1 number(s): "973784935"
Test #51:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
100 538211264 446996850 198712335 88186935 511282839 475860827 100608783 228565764 902567038 135104316 296988621 862165031 534713476 219065492 952394847 360765642 115950706 406637979 830568330 583155152 460052149 292077783 492463808 699608681 907452664 860188878 924819058 481330097 25974839 63007136...
output:
141497771
result:
ok 1 number(s): "141497771"
Test #52:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
100 312890580 393896274 480926841 664002432 584591137 999156300 632165548 387307346 849006310 582498034 431088142 993081763 615301849 286914158 544485567 69496805 166251264 396221725 576857318 296217058 622182283 709200948 311843446 303202668 526969939 826200595 15104678 540575137 400327406 96635078...
output:
808258237
result:
ok 1 number(s): "808258237"
Test #53:
score: 0
Accepted
time: 69ms
memory: 3996kb
input:
2000 8 14 18 0 10 10 1 8 5 11 14 4 5 6 10 3 20 19 16 12 20 10 5 7 16 15 2 17 1 2 19 9 0 0 10 4 2 11 19 13 16 15 14 20 17 14 2 5 8 16 17 11 4 7 9 4 16 13 5 0 4 1 11 11 14 14 17 1 12 3 13 13 15 10 2 1 3 3 13 18 4 16 15 14 20 14 0 5 2 3 0 9 6 7 10 15 2 11 3 15 18 17 6 11 3 12 7 9 14 20 16 10 7 18 9 3 3...
output:
958208391
result:
ok 1 number(s): "958208391"
Test #54:
score: 0
Accepted
time: 69ms
memory: 3760kb
input:
2000 13 15 17 7 2 16 19 20 16 3 20 0 17 11 0 2 4 20 20 7 3 15 18 17 11 8 13 13 0 0 15 18 1 4 1 12 19 17 9 0 15 12 13 6 12 8 18 19 0 16 10 17 1 15 11 1 14 7 15 5 2 18 11 6 13 13 15 9 10 16 10 15 1 11 1 8 9 2 6 20 0 14 4 2 18 12 10 0 2 0 14 20 4 6 10 16 2 16 9 20 1 13 8 16 9 15 5 9 20 1 13 3 11 6 5 19...
output:
715234756
result:
ok 1 number(s): "715234756"
Test #55:
score: 0
Accepted
time: 71ms
memory: 3724kb
input:
2000 6 4 2 4 6 14 9 7 1 3 17 4 0 13 16 10 0 20 8 19 11 20 15 1 6 13 3 9 2 15 8 7 2 8 9 4 3 14 17 4 13 18 8 14 15 14 13 17 20 2 7 19 3 18 17 19 15 15 4 7 0 5 8 9 7 12 17 0 7 12 16 12 7 8 17 7 2 10 20 18 12 11 6 10 19 15 17 11 6 1 7 2 2 6 9 3 10 0 2 0 17 12 14 4 7 17 4 20 10 20 7 13 19 2 2 17 20 4 6 2...
output:
22101785
result:
ok 1 number(s): "22101785"
Test #56:
score: 0
Accepted
time: 69ms
memory: 3960kb
input:
2000 10 9 13 1 10 3 2 10 15 13 3 4 8 1 19 9 4 13 20 7 8 0 11 6 10 7 19 19 18 5 8 0 3 11 13 12 17 16 20 20 8 16 2 0 10 8 7 6 4 1 5 0 4 5 2 12 12 9 14 8 6 17 8 20 2 3 11 16 8 8 1 13 9 1 12 6 17 1 5 17 0 17 20 2 13 18 7 2 6 2 4 9 17 13 4 11 5 17 16 18 0 7 19 4 17 12 2 3 4 1 5 15 2 7 15 20 0 17 20 7 12 ...
output:
173081608
result:
ok 1 number(s): "173081608"
Test #57:
score: 0
Accepted
time: 70ms
memory: 4032kb
input:
2000 15 19 12 12 14 6 20 5 13 5 0 8 20 2 19 4 0 9 20 6 16 5 11 7 5 17 9 15 20 20 4 2 8 3 4 8 13 8 15 7 6 13 18 8 5 2 2 0 17 0 2 14 2 13 8 14 9 12 7 17 4 1 8 15 18 19 13 6 10 12 6 7 19 19 11 13 2 0 19 6 13 19 5 15 11 12 10 14 1 4 6 8 16 12 3 7 17 5 9 2 12 3 4 13 19 14 17 10 19 3 6 4 9 8 12 10 13 18 2...
output:
689909392
result:
ok 1 number(s): "689909392"
Test #58:
score: 0
Accepted
time: 71ms
memory: 3992kb
input:
2000 20 20 2 9 14 16 9 8 7 18 6 12 11 4 1 20 5 10 12 18 20 19 7 12 3 1 20 11 15 18 18 12 13 7 12 20 14 14 18 11 17 19 16 6 8 0 18 18 17 3 20 16 16 17 10 19 10 7 1 18 18 1 1 1 12 10 11 14 11 8 4 4 1 20 6 20 17 12 13 8 14 17 11 20 8 11 16 9 1 1 3 11 6 19 7 15 13 10 2 7 20 2 2 18 0 9 16 14 17 19 17 14 ...
output:
525822114
result:
ok 1 number(s): "525822114"
Test #59:
score: 0
Accepted
time: 71ms
memory: 3732kb
input:
2000 3 1 9 19 1 6 3 16 0 10 12 8 2 5 0 20 10 2 4 10 3 20 4 17 7 16 18 3 17 8 14 8 10 11 3 8 11 3 13 15 12 17 11 10 3 15 12 16 9 7 18 18 13 13 16 12 4 14 7 2 15 5 1 7 7 8 13 9 8 4 6 5 3 1 5 19 19 19 6 11 6 2 0 16 6 10 10 0 13 2 17 15 8 19 2 11 8 7 8 12 11 2 8 6 19 12 10 1 6 4 19 16 8 13 1 12 13 2 13 ...
output:
587508108
result:
ok 1 number(s): "587508108"
Test #60:
score: 0
Accepted
time: 71ms
memory: 3724kb
input:
2000 17 10 7 17 5 12 0 3 2 3 6 12 6 15 3 15 5 3 20 5 7 4 8 5 2 17 9 20 15 3 6 18 16 14 11 0 7 13 16 14 10 19 10 0 19 0 11 14 17 2 15 20 11 20 1 9 1 8 4 3 17 13 5 10 2 7 15 0 6 0 12 7 9 19 0 1 13 2 20 9 19 4 10 3 7 12 17 16 13 3 10 5 19 18 5 19 16 12 1 13 6 14 14 6 8 6 16 0 0 10 8 5 16 13 19 2 14 15 ...
output:
895833705
result:
ok 1 number(s): "895833705"
Test #61:
score: 0
Accepted
time: 69ms
memory: 3960kb
input:
2000 0 16 18 2 5 2 10 10 0 3 16 8 18 3 3 14 10 20 16 4 8 9 0 11 14 10 3 16 14 1 3 3 13 14 19 16 12 5 20 18 9 16 0 4 1 15 2 11 13 13 4 5 4 3 16 14 6 11 10 8 19 0 19 9 0 19 9 8 3 13 17 17 15 12 7 9 11 10 5 7 6 2 12 8 1 15 2 7 12 9 3 8 17 4 1 15 11 17 15 18 10 18 20 19 10 9 14 12 19 12 10 19 20 1 11 1 ...
output:
263930283
result:
ok 1 number(s): "263930283"
Test #62:
score: 0
Accepted
time: 70ms
memory: 3680kb
input:
2000 7 11 11 8 17 17 10 0 9 19 6 11 3 8 3 15 5 14 13 17 12 10 13 1 3 10 4 20 11 11 8 0 17 15 12 11 3 4 17 14 3 4 6 9 0 20 11 14 6 1 4 1 8 0 7 1 3 5 10 18 17 15 1 15 1 11 4 9 14 7 16 1 11 9 10 1 12 15 7 5 3 17 1 19 3 4 14 6 1 1 5 7 9 16 2 13 19 6 7 11 10 1 9 5 19 19 9 11 5 8 10 14 15 2 17 3 19 3 17 1...
output:
728560648
result:
ok 1 number(s): "728560648"
Test #63:
score: 0
Accepted
time: 313ms
memory: 3824kb
input:
2000 565117304 125814888 586097543 963853833 196590927 534233702 214202996 417607347 217344493 833980730 579124249 288058518 353693152 141368 931819726 549915952 94544449 722578470 980780801 815164329 127100054 282936210 827026159 411803214 977935317 679355574 614170675 304267823 705937537 243835557...
output:
788046078
result:
ok 1 number(s): "788046078"
Test #64:
score: 0
Accepted
time: 309ms
memory: 3768kb
input:
2000 788436877 974052673 829967590 765398156 269539766 537102347 622553467 666401120 874506660 16535909 781745304 155828426 850228329 124196813 779920379 156915212 379354853 68702931 983430000 113473197 140287884 730520408 843204556 903083650 638242565 250586437 440501645 455899967 741443011 9088761...
output:
595061241
result:
ok 1 number(s): "595061241"
Test #65:
score: 0
Accepted
time: 317ms
memory: 3832kb
input:
2000 421821866 527323166 368804927 566942480 678925093 834938283 104532865 915194893 163072606 977752725 320802846 433663751 273134577 543219551 964457522 353849056 664165257 119860101 649642710 411782067 112006517 136635407 859382954 762960305 372178740 158253789 971865323 943968600 408352265 57391...
output:
125819098
result:
ok 1 number(s): "125819098"
Test #66:
score: 0
Accepted
time: 316ms
memory: 3824kb
input:
2000 350174147 375560950 317707681 73519512 751873932 132774218 512883337 532584885 451638553 160307904 523423900 301433659 769669754 962242288 517590884 255815609 612539173 171017271 20888128 5058227 420161639 879186897 875561351 959273449 737518696 729484653 798196293 432037231 738825031 238957199...
output:
85486072
result:
ok 1 number(s): "85486072"
Test #67:
score: 0
Accepted
time: 315ms
memory: 3832kb
input:
2000 942089940 223798734 561577727 170031127 529855479 430610155 994862736 781378658 445237208 711459303 62481442 874236276 561172221 749861245 775756954 789185942 897349577 885737953 687100840 303367096 433349469 695367313 891739748 745521177 471454872 300715516 329559970 878636667 110766993 609030...
output:
430396548
result:
ok 1 number(s): "430396548"
Test #68:
score: 0
Accepted
time: 322ms
memory: 4052kb
input:
2000 575474929 777069228 100415065 676608160 307837025 359849871 403213206 398768650 733803155 894014482 265102496 742006184 689111178 168883981 960294097 691152494 182159980 231862414 689750039 601675965 110100810 732886093 834289217 605397832 836794828 913415577 155890939 366705299 441239760 56903...
output:
521976850
result:
ok 1 number(s): "521976850"
Test #69:
score: 0
Accepted
time: 316ms
memory: 3860kb
input:
2000 503827210 330339720 49317819 109556263 85818572 657685807 885192605 647562423 685932614 445165881 99127331 609776092 185646354 292939427 513427459 593119047 466970384 283019584 355962749 194952125 418255932 844033802 850467615 96678267 570731004 484646440 687254618 854773932 108149014 307707768...
output:
807886658
result:
ok 1 number(s): "807886658"
Test #70:
score: 0
Accepted
time: 313ms
memory: 3896kb
input:
2000 432179491 178577505 293187865 911100588 790171192 660554451 998575785 559919707 974498561 37786476 301748385 182578708 977148823 80558384 66560821 421456671 46748080 629144046 22175459 493260994 726411054 250148801 866646012 587958703 231038251 55877303 808552879 637809856 143654488 972748316 7...
output:
984099271
result:
ok 1 number(s): "984099271"
Test #71:
score: 0
Accepted
time: 314ms
memory: 3828kb
input:
2000 360531772 731847998 832025203 417677620 568152738 958390388 480555183 513746188 263064507 588937876 840805928 755381325 105087778 499581121 956130672 323423223 700154704 975268508 319791951 791569864 403162395 697732998 882824409 447835358 670007135 332140876 339916556 789441999 810563743 63778...
output:
432195691
result:
ok 1 number(s): "432195691"
Test #72:
score: 0
Accepted
time: 310ms
memory: 3824kb
input:
2000 850674853 757678182 614338058 932025149 494408266 474957686 385076647 602473996 985457496 474129209 664895614 408386263 886629199 321087388 862987220 229618462 498766602 984642359 149906363 43490627 906658497 23053563 464000957 741736344 91234120 651257405 186319293 147794914 15917570 300028244...
output:
312721957
result:
ok 1 number(s): "312721957"
Test #73:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
3 0 0 0 0 1 1
output:
10
result:
ok 1 number(s): "10"
Test #74:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
5 0 0 0 0 1 1 1 1 1 1
output:
52
result:
ok 1 number(s): "52"
Test #75:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
3 0 0 0 0 0 0
output:
7
result:
ok 1 number(s): "7"