QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#23804 | #2959. Antialiasing | FudanU1# | AC ✓ | 8ms | 3892kb | C++20 | 5.8kb | 2022-03-19 15:16:37 | 2022-04-30 04:09:59 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define ge getchar
#define pun putchar('\n')
#define pu putchar
#define puk putchar(' ')
#define pb push_back
struct fr{
ll z,m;//m>0
};
struct dian{
fr x,y;
};
typedef vector<dian> ved;
int n;
fr f1_2={1,2},f0={0,1};
vector<dian>a;
dian q;
void yf(fr&a){
ll d=__gcd(a.z,a.m);
a.z/=d;a.m/=d;
}
fr operator *(fr a,fr b){
fr c;
c.z=a.z*b.z;
c.m=a.m*b.m;
yf(c);
return c;
}
fr operator +(fr a,fr b){
fr c;
c.z=a.z*b.m+a.m*b.z;
c.m=a.m*b.m;
yf(c);
return c;
}
fr operator -(fr a,fr b){
fr c;
c.z=a.z*b.m-a.m*b.z;
c.m=a.m*b.m;
yf(c);
return c;
}
fr operator /(fr a,fr b){
fr c;
c.z=a.z*b.m;
c.m=a.m*b.z;
yf(c);
if(c.m<0)c.m=-c.m,c.z=-c.z;
return c;
}
double va(fr a){return (double)a.z/a.m;}
bool operator ==(fr a,fr b){
return a.z==b.z&&a.m==b.m;
}
double mx,my;
fr ff(){
//y<=q.y+1/2
vector<dian>jd;
vector<int>yo;
fr yy=f1_2+q.y,xx;
dian u;u=a[n-1];
//printf("!\n");
for(int i=0;i<n;i++){
dian v=a[i];
if((va(yy)-va(v.y))*(va(yy)-va(u.y))<=0){
fr dx=v.x-u.x,dy=v.y-u.y;
//printf("%.6lf %.6lf \n",va(dx),va(dy));
xx=(yy-u.y)*dx/dy+u.x;
//jiaodian=(xx,yy) xx\in [v.x u.x]
if((va(xx)-va(v.x))*(va(xx)-va(u.x))<=0){
dian s={xx,yy};
if(!(s.x==v.x&&s.y==v.y)){
//printf("(%.6lf,%.6lf)\n",va(xx),va(yy));
jd.push_back(s);
yo.push_back(i);}
}
}
u=v;
}
int r=jd.size();
ved b;
if(r<=1){
if(my>va(yy))return f0;
b=a;
}else{
if(va(a[yo[0]].y)<=va(yy)){
b.pb(jd[1]);
b.pb(jd[0]);
int i=yo[0];
while(i!=yo[1]){
b.pb(a[i]);
i++;
if(i==a.size())i=0;
}
}else{
b.pb(jd[0]);
b.pb(jd[1]);
int i=yo[1];
while(i!=yo[0]){
b.pb(a[i]);
i++;
if(i==a.size())i=0;
}
}
}
//printf("!!\n");
/*printf("poly %d\n",b.size());
for(int i=0;i<b.size();i++){
printf("b(%.6lf,%.6lf)\n",va(b[i].x),va(b[i].y));
}*/
//y>=q.y-1/2
jd.clear();yo.clear();
yy=q.y-f1_2;
//printf("poly %d\n",b.size());
u=b[b.size()-1];
double yb=0.0;
for(int i=0;i<b.size();i++){
dian v=b[i];yb+=va(v.y);
if((va(yy)-va(v.y))*(va(yy)-va(u.y))<=0){
fr dx=v.x-u.x,dy=v.y-u.y;
xx=(yy-u.y)*dx/dy+u.x;
//jiaodian=(xx,yy) xx\in [v.x u.x]
if((va(xx)-va(v.x))*(va(xx)-va(u.x))<=0){
dian s={xx,yy};
if(!(s.x==v.x&&s.y==v.y)){
//printf("(%.6lf,%.6lf)\n",va(xx),va(yy));
jd.push_back(s);
yo.push_back(i);}
}
}
u=v;
}
yb/=b.size();
r=jd.size();
ved c;
if(r<=1){
if(yb<va(yy))return f0;
c=b;
}else{
if(va(b[yo[0]].y)>=va(yy)){
c.pb(jd[1]);
c.pb(jd[0]);
int i=yo[0];
while(i!=yo[1]){
c.pb(b[i]);
i++;
if(i==b.size())i=0;
}
}else{
c.pb(jd[0]);
c.pb(jd[1]);
int i=yo[1];
while(i!=yo[0]){
c.pb(b[i]);
i++;
if(i==b.size())i=0;
}
}
}
//printf("!!!\n");
/*printf("poly %d\n",c.size());
for(int i=0;i<c.size();i++){
printf("c(%.6lf,%.6lf)\n",va(c[i].x),va(c[i].y));
}*/
//x<=q.x+1/2
jd.clear();yo.clear();
xx=q.x+f1_2;
u=c[c.size()-1];
double xc=0.0;
for(int i=0;i<c.size();i++){
dian v=c[i];xc+=va(v.x);
if((va(xx)-va(v.x))*(va(xx)-va(u.x))<=0){
fr dx=v.x-u.x,dy=v.y-u.y;
yy=(xx-u.x)*dy/dx+u.y;
//jiaodian=(xx,yy) xx\in [v.x u.x]
if((va(yy)-va(v.y))*(va(yy)-va(u.y))<=0){
dian s={xx,yy};
if(!(s.x==v.x&&s.y==v.y)){
//printf("(%.6lf,%.6lf)\n",va(xx),va(yy));
jd.push_back(s);
yo.push_back(i);}
}
}
u=v;
}
xc/=c.size();
r=jd.size();
b.clear();
if(r<=1){
if(xc>va(xx))return f0;
b=c;
}else{
if(va(c[yo[0]].x)<=va(xx)){
b.pb(jd[1]);
b.pb(jd[0]);
int i=yo[0];
while(i!=yo[1]){
b.pb(c[i]);
i++;
if(i==c.size())i=0;
}
}else{
b.pb(jd[0]);
b.pb(jd[1]);
int i=yo[1];
while(i!=yo[0]){
b.pb(c[i]);
i++;
if(i==c.size())i=0;
}
}
}
/*printf("!!!!\n");
//x>=q.x-1/2
printf("poly %d\n",b.size());
for(int i=0;i<b.size();i++){
printf("b(%.6lf,%.6lf)\n",va(b[i].x),va(b[i].y));
}*/
jd.clear();yo.clear();
xx=q.x-f1_2;
u=b[b.size()-1];
double xb=0.0;
for(int i=0;i<b.size();i++){
dian v=b[i];xb+=va(v.x);
if((va(xx)-va(v.x))*(va(xx)-va(u.x))<=0){
fr dx=v.x-u.x,dy=v.y-u.y;
yy=(xx-u.x)*dy/dx+u.y;
//jiaodian=(xx,yy) xx\in [v.x u.x]
if((va(yy)-va(v.y))*(va(yy)-va(u.y))<=0){
dian s={xx,yy};
if(!(s.x==v.x&&s.y==v.y)){
//printf("(%.6lf,%.6lf)\n",va(xx),va(yy));
jd.push_back(s);
yo.push_back(i);}
}
}
u=v;
}
xb/=b.size();
r=jd.size();
c.clear();
if(r<=1){
if(xb<va(xx))return f0;
c=b;
}else{//printf("poly %d\n",b.size());
if(va(b[yo[0]].x)>=va(xx)){
c.pb(jd[1]);
c.pb(jd[0]);
int i=yo[0];
while(i!=yo[1]){
c.pb(b[i]);
i++;
if(i==b.size())i=0;
}
}else{
c.pb(jd[0]);
c.pb(jd[1]);
int i=yo[1];
while(i!=yo[0]){
c.pb(b[i]);
i++;
if(i==b.size())i=0;
}
}
}
//printf("poly %d\n",c.size());
//area c
fr s={0,1};
dian w=c[0];
u=c[1];
for(int i=2;i<c.size();i++){
dian v=c[i];//u*v
s=s+(u.x-w.x)*(v.y-w.y)-(u.y-w.y)*(v.x-w.x);
u=v;
}
s.m*=2;
yf(s);
//printf("%d %.6lf\n",c.size(),va(s));
return s;
}
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
scanf("%d",&n);
int tt;scanf("%d",&tt);
mx=my=0.0;
for(int i=1;i<=n;i++){
dian o;o.x.m=o.y.m=1;
scanf("%lld%lld",&o.x.z,&o.y.z);
mx+=va(o.x);my+=va(o.y);
a.push_back(o);
}
mx/=n;my/=n;
q.x.m=q.y.m=1;
while(tt--){
scanf("%lld%lld",&q.x.z,&q.y.z);
fr s=ff();
printf("%lld/%lld\n",s.z,s.m);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3700kb
input:
4 4 1 1 4 1 4 4 1 4 3 3 10 10 1 3 1 4
output:
1/1 0/1 1/2 1/4
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
3 4 1 1 11 11 1 21 1 1 11 11 21 1 4 4
output:
1/8 1/4 0/1 1/2
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 3ms
memory: 3748kb
input:
4 6 10 10 11 10 11 11 10 11 10 10 11 10 11 11 10 11 9 10 11 12
output:
1/4 1/4 1/4 1/4 0/1 0/1
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
4 999 0 0 1000 0 1000 1000 0 1000 0 0 1000 0 1000 1000 0 1000 483 55 841 0 116 1000 0 212 1000 809 43 400 439 0 769 1000 0 106 1000 175 419 275 755 0 565 1000 0 531 1000 959 11 736 982 0 254 1000 0 965 1000 975 208 472 164 0 732 1000 0 133 1000 18 780 203 977 0 223 1000 0 772 1000 227 398 600 729 0 ...
output:
1/4 1/4 1/4 1/4 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 ...
result:
ok 999 lines
Test #5:
score: 0
Accepted
time: 5ms
memory: 3692kb
input:
3 993 0 0 1000 500 0 1000 0 0 1000 500 0 1000 11 383 0 954 806 403 806 404 806 402 636 628 0 826 880 440 880 441 880 439 701 686 0 957 250 125 250 126 250 124 137 469 0 341 180 90 180 91 180 89 638 267 0 495 770 385 770 386 770 384 723 110 0 577 46 23 46 24 46 22 250 56 0 224 446 223 446 224 446 222...
output:
3/16 1/8 3/16 1/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 1/1 1/...
result:
ok 993 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 3692kb
input:
4 64 1 1 5 2 5 5 1 6 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 6 0 6 1 6 2 6 3 6 4 6 5 6 6 6 7 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7
output:
0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 7/32 1/2 1/2 1/2 1/2 7/32 0/1 0/1 1/4 1/1 1/1 1/1 1/1 1/4 0/1 0/1 1/32 31/32 1/1 1/1 31/32 1/32 0/1 0/1 0/1 3/4 1/1 1/1 3/4 0/1 0/1 0/1 0/1 9/32 1/2 1/2 9/32 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1
result:
ok 64 lines
Test #7:
score: 0
Accepted
time: 6ms
memory: 3760kb
input:
100 999 0 0 1000 500 998 501 996 502 994 503 992 504 990 505 988 506 986 507 984 508 982 509 980 510 978 511 976 512 974 513 972 514 970 515 968 516 966 517 964 518 962 519 960 520 958 521 956 522 954 523 952 524 950 525 948 526 946 527 944 528 942 529 940 530 938 531 936 532 934 533 932 534 930 535...
output:
3/16 1/8 3/16 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/...
result:
ok 999 lines
Test #8:
score: 0
Accepted
time: 7ms
memory: 3788kb
input:
10 1000 1000 83 993 569 990 675 976 958 969 982 870 993 374 999 1 1000 0 0 482 0 1000 83 993 569 990 675 976 958 969 982 870 993 374 999 1 1000 0 0 482 0 102 800 569 366 623 371 296 429 735 83 872 500 61 864 611 578 184 642 210 796 302 16 723 865 227 354 290 167 970 724 757 902 227 858 13 681 900 74...
output:
33763/125874 51337/103032 119357/239984 25523/54336 173/576 8707/17856 369145/740032 745373/2984000 1999/8000 1989/4144 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 ...
result:
ok 1000 lines
Test #9:
score: 0
Accepted
time: 6ms
memory: 3832kb
input:
10 1000 1000 164 999 446 996 653 985 898 966 962 910 984 619 999 381 999 162 998 69 993 1000 164 999 446 996 653 985 898 966 962 910 984 619 999 381 999 162 998 69 993 671 117 755 386 177 56 262 542 35 802 772 415 970 45 338 947 933 571 496 412 652 567 937 433 910 789 964 657 68 253 85 686 941 566 2...
output:
290375/2100336 25873/51888 33553/67620 58769/125440 1205/3584 9937/21728 383/776 875/1752 13411/27156 10219/86583 0/1 1/1 0/1 0/1 0/1 1/1 0/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 0/1 0/1 1/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 1/1 0/1 0/1 1/1 0/1 0/1 0/1 0/1 1/1 1/1 1/1 0/1 0/1 0/1 0/1 1/1 0/1 0/1 1/1 0/1 0/1 1/...
result:
ok 1000 lines
Test #10:
score: 0
Accepted
time: 7ms
memory: 3840kb
input:
20 1000 1000 514 1000 723 998 879 987 971 922 984 723 992 191 1000 13 986 6 962 0 621 0 541 1 73 13 20 304 2 547 1 737 7 954 27 976 90 986 139 996 223 1000 514 1000 723 998 879 987 971 922 984 723 992 191 1000 13 986 6 962 0 621 0 541 1 73 13 20 304 2 547 1 737 7 954 27 976 90 986 139 996 223 529 75...
output:
145/291 311/624 13969/28704 1067/3680 3821/7960 52601/105868 46239/94696 5063/17088 30493/65472 679/1364 1871/3744 93653/198432 2941/10282 92923/188568 22879/46170 81211/164920 596/1953 425/882 1151/2352 5289/10864 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1...
result:
ok 1000 lines
Test #11:
score: 0
Accepted
time: 7ms
memory: 3752kb
input:
20 1000 999 315 998 998 891 999 556 999 439 999 196 999 148 994 1 946 0 621 0 313 1 244 5 102 9 55 48 22 53 21 473 1 949 0 980 13 995 127 997 144 999 315 998 998 891 999 556 999 439 999 196 999 148 994 1 946 0 621 0 313 1 244 5 102 9 55 48 22 53 21 473 1 949 0 980 13 995 127 997 144 160 321 548 651 ...
output:
465635/934344 18369/73081 427/856 1/2 1/2 187/384 8885/18816 37099/127400 1299/2600 275/552 19529/39192 6579/13348 1791/4888 109/260 101/210 5647/11424 52805/118048 3005/9424 2575/5168 1415/2907 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 3/68 1/1 1/2 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 ...
result:
ok 1000 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
19 1000 1000 29 996 627 988 850 977 968 946 996 710 1000 455 998 107 990 30 968 12 933 2 848 0 621 1 81 16 44 69 0 481 1 859 8 902 12 982 23 1000 29 996 627 988 850 977 968 946 996 710 1000 455 998 107 990 30 968 12 933 2 848 0 621 1 81 16 44 69 0 481 1 859 8 902 12 982 23 660 506 908 699 737 861 56...
output:
2087/7176 132381/266708 103747/210512 10961/29264 5695/14632 59807/120360 7367/14790 569/1218 7/20 268/595 1877/3859 489013/980640 71857/159840 6345/15688 69163/174688 44317/88992 9115/18576 13607/27520 913/1920 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 ...
result:
ok 1000 lines
Test #13:
score: 0
Accepted
time: 6ms
memory: 3792kb
input:
20 1000 1000 162 1000 626 997 906 995 965 955 980 833 999 616 1000 24 992 15 976 4 944 3 901 0 621 12 161 18 64 105 13 156 7 396 1 929 3 982 23 997 48 1000 162 1000 626 997 906 995 965 955 980 833 999 616 1000 24 992 15 976 4 944 3 901 0 621 12 161 18 64 105 13 156 7 396 1 929 3 982 23 997 48 776 85...
output:
151/304 1117/2240 65697/132160 1137/3776 1845/3904 101895/211792 63941/128464 1525/4736 121/256 5063/11008 48009/96320 25523/51520 44221/89240 7449/22504 1741/3944 2657/5440 84667/170560 51221/112996 789/2120 651/1520 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/...
result:
ok 1000 lines
Test #14:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
22 1000 1000 565 999 953 941 993 867 999 516 1000 201 1000 179 1000 58 999 39 989 19 968 12 949 0 621 1 117 5 64 26 27 56 8 130 0 698 0 835 0 924 2 989 25 997 48 1000 565 999 953 941 993 867 999 516 1000 201 1000 179 1000 58 999 39 989 19 968 12 949 0 621 1 117 5 64 26 27 56 8 130 0 698 0 835 0 924 ...
output:
800703/1604768 30293/90016 3639/8584 12733/25974 1403/2808 1/2 483/968 8005/18392 347/798 1363/3192 5715/12464 81859/165312 104885/213696 6879/15688 3553/8880 3857/8880 18/37 1/2 177/356 21223/46280 4039/11960 43497/95128 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/...
result:
ok 1000 lines
Test #15:
score: 0
Accepted
time: 6ms
memory: 3696kb
input:
21 1000 1000 505 1000 933 962 971 865 997 529 1000 235 1000 123 1000 49 983 10 923 3 756 0 621 0 259 6 178 7 167 17 104 30 56 74 12 179 4 368 0 881 1 997 48 1000 505 1000 933 962 971 865 997 529 1000 235 1000 123 1000 49 983 10 923 3 756 0 621 0 259 6 178 7 167 17 104 30 56 74 12 179 4 368 0 881 1 9...
output:
1825/3656 3/8 317/776 40641/86912 447/896 1/2 279/592 2131/5920 11329/26720 3739/7515 179/360 53/108 1183/2376 2725/5544 3919/8064 157/384 323/840 466/945 14281/28728 214037/476064 127851/424096 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1...
result:
ok 1000 lines
Test #16:
score: 0
Accepted
time: 6ms
memory: 3756kb
input:
21 1000 997 48 997 932 997 983 976 991 886 995 768 996 479 997 365 996 279 995 53 992 20 985 0 923 0 740 0 621 0 586 1 164 2 11 205 1 943 2 968 15 973 18 997 48 997 932 997 983 976 991 886 995 768 996 479 997 365 996 279 995 53 992 20 985 0 923 0 740 0 621 0 586 1 164 2 11 205 1 943 2 968 15 973 18 ...
output:
2/5 1/2 25/84 577/1260 21049/42480 136237/272816 131381/263568 9797/19608 4857/9718 28349/59664 2593/8184 57/124 1/2 1/2 1687/3376 257995/516528 63851/248472 591673/1198512 64231/147600 49/100 17/40 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1...
result:
ok 1000 lines
Test #17:
score: 0
Accepted
time: 6ms
memory: 3784kb
input:
18 1000 999 156 998 597 996 850 995 921 990 989 733 1000 528 1000 29 998 13 970 0 923 0 242 10 42 28 24 113 0 887 0 951 1 973 18 987 33 999 156 998 597 996 850 995 921 990 989 733 1000 528 1000 29 998 13 970 0 923 0 242 10 42 28 24 113 0 887 0 951 1 973 18 987 33 965 725 937 282 361 660 364 285 300 ...
output:
70519/144648 445663/892584 71741/143704 19025/38624 36985/139808 1017/2056 997/1996 2249/6986 1219/2632 175/376 79/160 61/160 279/680 79/170 255/512 2283/5632 1223/2640 973/2460 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/...
result:
ok 1000 lines
Test #18:
score: 0
Accepted
time: 7ms
memory: 3836kb
input:
17 1000 999 983 906 988 752 993 62 999 23 990 1 930 0 923 5 4 661 1 793 1 951 1 973 18 987 33 995 176 996 198 997 273 998 589 999 983 906 988 752 993 62 999 23 990 1 930 0 923 5 4 661 1 793 1 951 1 973 18 987 33 995 176 996 198 997 273 998 589 754 407 483 911 905 23 346 118 895 457 883 331 804 218 2...
output:
75161/293136 56983/114576 70419/141680 2811/5980 1013/3120 793/1680 12389/25732 1211765/4822912 2621/5248 1/2 71/176 1223/2640 3349/8580 1141/2288 6547/13200 94559/189600 248969/498016 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1...
result:
ok 1000 lines
Test #19:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
16 1000 998 297 998 397 998 589 996 954 995 961 952 992 946 996 51 1000 0 923 0 164 1 71 12 15 113 2 570 0 992 3 996 198 998 297 998 397 998 589 996 954 995 961 952 992 946 996 51 1000 0 923 0 164 1 71 12 15 113 2 570 0 992 3 996 198 126 205 131 699 431 702 66 119 691 701 587 518 921 95 381 549 856 ...
output:
197/396 1/2 729/1460 9869/20440 431/1204 509/1032 4481/10740 183167/551320 257/616 371/744 19865/41664 13151/45248 178889/369256 769201/1542832 166853/658320 12869/25740 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/...
result:
ok 1000 lines
Test #20:
score: 0
Accepted
time: 6ms
memory: 3892kb
input:
16 1000 1000 480 1000 823 999 995 712 1000 535 1000 85 996 28 995 0 923 0 426 3 59 18 22 51 10 83 5 120 2 992 3 999 88 1000 480 1000 823 999 995 712 1000 535 1000 85 996 28 995 0 923 0 426 3 59 18 22 51 10 83 5 120 2 992 3 999 88 440 880 481 982 486 601 579 571 288 496 433 66 911 661 897 126 782 945...
output:
1567/3136 687/1376 99875/394912 1143/2296 449/900 17063/34200 823/2736 65/144 1465/2936 24461/54316 1127/3256 1335/2816 4647/9472 126403/258112 154429/592960 130621/266560 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 ...
result:
ok 1000 lines
Test #21:
score: 0
Accepted
time: 7ms
memory: 3836kb
input:
18 1000 1000 619 1000 835 992 939 988 984 831 999 500 999 446 999 347 999 3 996 0 923 0 918 0 700 4 23 74 5 372 0 569 0 992 3 999 88 1000 619 1000 835 992 939 988 984 831 999 500 999 446 999 347 999 3 996 0 923 0 918 0 700 4 23 74 5 372 0 569 0 992 3 999 88 971 323 816 624 912 785 970 83 344 809 420...
output:
2123/4248 51/104 2333/4680 15433/56520 613/1256 1/2 1/2 1373/2752 51475/200896 289/584 1/2 338/677 53623/189560 39213/83440 1187/2384 563/1128 12521/47940 44227/90270 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/2 1/1 1...
result:
ok 1000 lines
Test #22:
score: 0
Accepted
time: 7ms
memory: 3800kb
input:
18 1000 999 88 999 220 999 415 998 999 640 1000 616 1000 575 1000 315 1000 112 1000 19 966 0 923 5 184 8 102 26 10 161 4 282 3 834 0 986 1 999 88 999 220 999 415 998 999 640 1000 616 1000 575 1000 315 1000 112 1000 19 966 0 923 5 184 8 102 26 10 161 4 282 3 834 0 986 1 153 524 467 111 34 748 632 878...
output:
335/696 1/2 2335/4672 209543/836288 1431/2864 1/2 1/2 1/2 169/372 11227/31992 28213/63554 240585/484784 1811/3772 4637/16560 21583/43560 88993/178112 6971/13984 28511/105792 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/...
result:
ok 1000 lines
Test #23:
score: 0
Accepted
time: 4ms
memory: 3724kb
input:
18 1000 999 220 998 298 984 981 979 995 788 1000 119 999 69 997 0 923 0 802 0 630 0 521 0 111 6 21 41 5 385 0 834 0 986 1 991 46 999 220 998 298 984 981 979 995 788 1000 119 999 69 997 0 923 0 802 0 630 0 521 0 111 6 21 41 5 385 0 834 0 986 1 991 46 147 414 791 333 495 898 503 777 860 97 366 909 430...
output:
8915/18096 212687/426192 35029/76496 6373/21392 126895/255558 8282/16725 5499/14800 227/592 1/2 1/2 1/2 59/120 53/168 42831/96320 1371/2752 607/1216 2897/10944 1027/2088 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/...
result:
ok 1000 lines
Test #24:
score: 0
Accepted
time: 6ms
memory: 3836kb
input:
16 1000 1000 31 1000 413 997 972 992 977 951 985 887 994 130 1000 82 996 13 975 0 923 0 741 0 233 1 64 13 5 824 0 986 1 1000 31 1000 413 997 972 992 977 951 985 887 994 130 1000 82 996 13 975 0 923 0 741 0 233 1 64 13 5 824 0 986 1 228 130 424 658 960 693 636 768 696 706 711 209 119 240 178 639 797 ...
output:
53/120 2233/4472 210/559 131/328 10353/20992 187363/387584 35507/72672 1043/2208 235/736 15/32 1/2 675/1352 37915/79768 105725/382792 523907/1051056 2003/6480 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1...
result:
ok 1000 lines
Test #25:
score: 0
Accepted
time: 3ms
memory: 3892kb
input:
19 1000 1000 588 1000 825 989 964 988 976 987 985 967 996 811 999 126 998 15 993 0 984 0 923 4 103 12 24 18 10 143 3 351 1 824 0 986 1 998 17 1000 588 1000 825 989 964 988 976 987 985 967 996 811 999 126 998 15 993 0 984 0 923 4 103 12 24 18 10 143 3 351 1 824 0 986 1 998 17 820 266 461 326 244 895 ...
output:
1141/2284 545/1112 6665/13344 143/288 479/1440 451/1040 141743/284960 150413/304140 239/555 13/40 819/1640 63219/129560 2031/4424 1087/3500 51397/104000 196399/393536 305869/613008 893/2592 7431/18272 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1...
result:
ok 1000 lines
Test #26:
score: 0
Accepted
time: 3ms
memory: 3752kb
input:
13 1000 1000 235 996 965 885 988 645 997 303 1000 86 998 0 984 2 13 69 5 401 0 840 2 966 4 998 17 1000 235 996 965 885 988 645 997 303 1000 86 998 0 984 2 13 69 5 401 0 840 2 966 4 998 17 977 287 558 841 999 41 184 55 756 273 831 328 750 878 184 499 261 200 466 897 977 592 508 962 994 114 233 779 38...
output:
158557/318280 89647/324120 34013/71040 18109/36480 98507/197904 35891/74648 90217/334024 17252/65057 86655/177952 580133/1165984 110315/221256 7277/16128 8425/27904 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1...
result:
ok 1000 lines
Test #27:
score: 0
Accepted
time: 8ms
memory: 3824kb
input:
15 1000 1000 35 1000 558 997 946 867 978 855 980 728 1000 170 1000 38 992 0 984 1 417 4 363 30 25 66 1 966 4 999 13 1000 35 1000 558 997 946 867 978 855 980 728 1000 170 1000 38 992 0 984 1 417 4 363 30 25 66 1 966 4 999 13 918 161 109 193 431 411 8 131 383 116 295 157 46 863 114 245 877 461 182 79 ...
output:
87/176 1549/3104 56843/201760 1529/3120 3041/6096 61/127 65/132 1207/2508 23795/86184 4475/9072 931/1872 107/312 333/800 12311/26400 51/176 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 ...
result:
ok 1000 lines
Test #28:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
4 4 3 0 5 4 3 8 1 4 3 0 5 4 3 8 1 4
output:
1/8 3/8 1/8 3/8
result:
ok 4 lines
Test #29:
score: 0
Accepted
time: 3ms
memory: 3844kb
input:
4 4 0 2 4 0 8 2 4 4 0 2 4 0 8 2 4 4
output:
1/8 3/8 1/8 3/8
result:
ok 4 lines