QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#238378 | #7680. Subway | ucup-team266# | WA | 1ms | 3688kb | C++14 | 3.5kb | 2023-11-04 16:33:45 | 2023-11-04 16:33:45 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
#define pdd pair<double,double>
const double eps=1e-9;
pdd operator +(pdd x,pdd y)
{
return mp(x.fi+y.fi,x.se+y.se);
}
pdd operator -(pdd x,pdd y)
{
return mp(x.fi-y.fi,x.se-y.se);
}
pdd operator *(pdd x,double y)
{
return mp(x.fi*y,x.se*y);
}
double dot(pdd x,pdd y)
{
return x.fi*y.fi+x.se*y.se;
}
double det(pdd x,pdd y)
{
return x.fi*y.se-y.fi*x.se;
}
// point q on seg p1--p2
bool onseg(pdd p1,pdd p2,pdd q)
{
return fabs(det(p1-q,p2-q))<eps&&dot(p1-q,p2-q)<eps;
}
// line p1--p2 q1--q2 intersection
bool good(pdd p1,pdd p2,pdd q1,pdd q2)
{
if(fabs(det(q2-q1,p2-p1))<eps) return 0;
return 1;
}
pdd inter(pdd p1,pdd p2,pdd q1,pdd q2)
{
if(fabs(det(p1-q1,p2-q2))<eps) return mp(-114514.0,-114514.0);
return p1+(p2-p1)*(det(q2-q1,q1-p1)/det(q2-q1,p2-p1));
}
// if seg p1--q1 p2--q2 has intersection
bool hascommon(pdd p1,pdd q1,pdd p2,pdd q2)
{
if(fabs(det(p1-q1,p2-q2))<eps) return onseg(p1,q1,p2)||onseg(p1,q1,q2)||onseg(p2,q2,p1)||onseg(p2,q2,q1);
pdd tmp=inter(p1,q1,p2,q2);
return onseg(p1,q1,tmp)&&onseg(p2,q2,tmp);
}
int n;
array<int,3> A[55];
int B[55];
mt19937_64 rnd(114514);
int gen_range(int l,int r)
{
return l+rnd()%(r-l+1);
}
const int K=20001;
vector <pii > pts[55];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>A[i][0]>>A[i][1]>>A[i][2],A[i][0]+=1001,A[i][1]+=1001;
sort(A+1,A+1+n);
int maxx=0;
for(int i=1;i<=n;i++) maxx=max(maxx,A[i][2]);
cout<<maxx<<"\n";
if(n==1)
{
while(maxx--)
{
int x=rnd()%1000000000,y=rnd()%1000000000;
cout<<2<<" "<<x<<" "<<y<<" "<<A[1][0]-1001<<" "<<A[1][1]-1001<<"\n";
}
return;
}
for(int i=1;i+1<=n;i++)
{
int b=A[i][1]+K*A[i][0]/2;
b++;
for(int x=2;pts[i].size()<=50;x+=2)
{
int y=x/2*(-K)+b;
if(y<0) pts[i].pb(mp(x,y));
}
}
vector <pair<pdd,pdd > > seg;
for(int i=1;i<=maxx;i++)
{
vector <pii > vec;
for(int j=1;j<=n;j++)
{
if(A[j][2]>=i) vec.pb(mp(A[j][0],A[j][1]));
if(j<n) vec.pb(pts[j][0]),pts[j].erase(pts[j].begin());
}
cout<<vec.size()<<" ";
for(int j=0;j<vec.size();j++) vec[j].fi-=1001,vec[j].se-=1001;
for(int j=0;j<vec.size();j++)
{
cout<<vec[j].fi<<" "<<vec[j].se<<" ";
if(j+1<vec.size()) seg.pb(mp((pdd)(vec[j]),(pdd)(vec[j+1])));
}
cout<<"\n";
}
// for(int i=0;i<seg.size();i++) for(int j=i+1;j<seg.size();j++) if(hascommon(seg[i].fi,seg[i].se,seg[j].fi,seg[j].se))
// {
// pdd t=inter(seg[i].fi,seg[i].se,seg[j].fi,seg[j].se);
// cout<<"inter: \n"<<seg[i].fi.fi<<" "<<seg[i].fi.se<<" --- "<<seg[i].se.fi<<" "<<seg[i].se.se<<"\n";
// cout<<seg[j].fi.fi<<" "<<seg[j].fi.se<<" "<<seg[j].se.fi<<" "<<seg[j].se.se<<"\n"<<t.fi<<" "<<t.se<<"\n";
// }
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3420kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 5 1 2 3 -19998 2 1 3 -9999 3 3 4 5 -39999 2 1 5 -30000 3 3
result:
ok ok Sum L = 9
Test #2:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
1 1 1 1
output:
1 2 9941593 465045846 1 1
result:
ok ok Sum L = 2
Test #3:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
1 1 1 50
output:
50 2 9941593 465045846 1 1 2 563161747 602690976 1 1 2 259930786 653941199 1 1 2 736786988 927523822 1 1 2 770306980 400709988 1 1 2 575439404 249360823 1 1 2 655022682 149297331 1 1 2 879309450 972458263 1 1 2 912537149 954600015 1 1 2 721227673 253933417 1 1 2 350100715 783388359 1 1 2 899999960 9...
result:
ok ok Sum L = 100
Test #4:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
50 662 -567 48 728 -120 7 307 669 27 -885 -775 21 100 242 9 -784 -537 41 940 198 46 736 -551 30 -449 456 16 -945 382 18 -182 810 49 213 187 44 853 245 48 617 -305 19 -81 261 3 617 208 8 -548 -652 6 -888 -667 14 -371 -812 43 202 -702 10 -668 -725 5 961 -919 33 -870 -697 50 428 810 29 560 405 7 348 -3...
output:
50 99 -981 -193 -979 -20193 -945 382 -943 -19618 -926 671 -925 -9329 -888 -667 -887 -10667 -885 -775 -883 -20775 -870 -697 -869 -10697 -825 381 -823 -19619 -784 -537 -783 -10537 -683 731 -681 -19269 -668 -725 -667 -10725 -579 -437 -577 -20437 -558 825 -557 -9175 -548 -652 -547 -10652 -499 -177 -497 ...
result:
ok ok Sum L = 3643
Test #5:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
50 -772 697 1 -756 -909 1 659 923 1 850 471 1 260 -24 1 473 -639 1 -575 393 1 -466 197 1 333 -637 1 -192 -890 1 103 546 1 749 -723 1 -573 613 1 214 -138 1 277 928 1 266 291 1 911 275 1 -680 -67 1 69 190 1 -197 -795 1 684 618 1 729 -115 1 -658 -229 1 -595 -470 1 898 -172 1 401 81 1 133 685 1 223 400 ...
output:
1 99 -772 697 -771 -9303 -756 -909 -755 -10909 -680 -67 -679 -10067 -666 -82 -665 -10082 -658 -229 -657 -10229 -595 -470 -593 -20470 -575 393 -573 -19607 -573 613 -571 -19387 -571 -716 -569 -20716 -532 838 -531 -9162 -530 890 -529 -9110 -466 197 -465 -9803 -389 708 -387 -19292 -346 458 -345 -9542 -3...
result:
ok ok Sum L = 99
Test #6:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
50 -56 747 3 993 -490 4 930 -139 1 -298 -330 1 938 -351 5 -973 100 5 -472 44 4 345 628 5 481 -91 4 789 581 5 457 -29 4 871 -799 1 692 994 4 699 854 2 893 -33 1 -483 256 3 -962 -540 2 846 -893 1 830 609 5 845 -383 2 -552 -966 1 -544 -51 1 564 186 4 -615 -675 1 618 -911 3 -561 -302 4 -293 667 3 -334 -...
output:
5 99 -999 330 -997 -19670 -973 100 -971 -19900 -962 -540 -961 -10540 -888 -613 -887 -10613 -842 381 -841 -9619 -792 -625 -791 -10625 -637 -801 -635 -20801 -615 -675 -613 -20675 -561 -302 -559 -20302 -552 -966 -551 -10966 -544 -51 -543 -10051 -483 256 -481 -19744 -472 44 -471 -9956 -364 169 -363 -983...
result:
ok ok Sum L = 386
Test #7:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
50 600 997 5 -893 -204 3 408 443 1 -560 -748 7 -647 161 6 -285 -980 1 87 -582 7 -48 -721 7 997 285 2 -189 -728 8 525 222 4 -324 816 9 760 317 3 753 -480 10 -813 -921 3 -325 -875 8 -747 816 10 -627 605 7 775 786 6 136 -54 2 274 948 10 216 -113 7 924 68 3 101 576 8 60 -501 2 898 801 8 -767 -974 10 -99...
output:
10 99 -982 -212 -981 -10212 -980 753 -979 -9247 -972 -312 -971 -10312 -893 -204 -891 -20204 -813 -921 -811 -20921 -805 -304 -803 -20304 -767 -974 -765 -20974 -747 816 -745 -19184 -660 -335 -659 -10335 -647 161 -645 -19839 -627 605 -625 -19395 -560 -748 -559 -10748 -498 -458 -497 -10458 -419 564 -417...
result:
ok ok Sum L = 771
Test #8:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
50 24 -889 49 117 418 49 25 524 44 980 -416 43 -494 357 41 -287 -285 46 151 574 41 -289 68 49 -515 -540 41 -367 -178 47 -887 151 45 197 -272 47 714 724 45 -737 94 49 810 830 47 808 -695 41 537 -637 49 -142 -167 44 -749 -631 47 445 -444 42 801 910 43 59 363 42 -912 466 50 -649 -479 48 -958 -511 49 88...
output:
50 99 -998 343 -997 -9657 -958 -511 -957 -10511 -912 466 -911 -9534 -887 151 -885 -19849 -868 -114 -867 -10114 -786 -384 -785 -10384 -749 -631 -747 -20631 -737 94 -735 -19906 -649 -479 -647 -20479 -615 809 -613 -19191 -588 -138 -587 -10138 -515 -540 -513 -20540 -494 357 -493 -9643 -486 866 -485 -913...
result:
ok ok Sum L = 4718
Test #9:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
50 151 -171 50 -367 -951 50 808 569 50 150 -618 50 27 -476 50 -846 729 50 549 -456 50 50 646 50 294 -70 50 -571 104 50 128 -265 50 913 -700 50 267 -965 50 896 846 50 -2 713 50 21 679 50 -515 975 50 168 180 50 -369 -98 50 676 115 50 643 -779 50 920 -237 50 -324 450 50 149 -378 50 -882 -602 50 -126 -7...
output:
50 99 -882 -602 -881 -10602 -851 279 -849 -19721 -846 729 -845 -9271 -841 601 -839 -19399 -604 -168 -603 -10168 -571 104 -569 -19896 -544 307 -543 -9693 -515 975 -513 -19025 -501 927 -499 -19073 -474 780 -473 -9220 -369 -98 -367 -20098 -367 -951 -365 -20951 -335 56 -333 -19944 -324 450 -323 -9550 -3...
result:
ok ok Sum L = 4950
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 3688kb
input:
50 4 5 34 1 -5 24 -4 -4 32 -3 3 28 0 -1 21 1 -4 25 0 0 30 0 -4 42 -3 -2 44 -5 -3 37 4 -1 46 5 2 20 2 2 37 -2 5 35 -2 -1 39 2 4 32 -4 -3 42 0 3 32 3 5 47 -4 1 2 5 -1 17 -5 -4 5 -2 2 29 -5 1 11 2 -5 43 4 4 14 -5 0 9 0 -5 17 5 1 27 -3 0 24 -1 4 16 5 0 50 3 -2 18 1 -2 6 2 -1 29 -1 3 38 1 5 36 -3 1 28 -3...
output:
50 99 -5 -4 -3 -20004 -5 -3 -3 -20003 -5 0 -3 -20000 -5 1 -3 -19999 -4 -4 -3 -10004 -4 -3 -3 -10003 -4 1 -3 -9999 -3 -3 -1 -20003 -3 -2 -1 -20002 -3 -1 -1 -20001 -3 0 -1 -20000 -3 1 -1 -19999 -3 3 -1 -19997 -3 5 -1 -19995 -2 -5 -1 -10005 -2 -1 -1 -10001 -2 2 -1 -9998 -2 5 -1 -9995 -1 -4 1 -20004 -1 ...
result:
wrong answer Polyline 2 intersects with previous polylines.