QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241321 | #7680. Subway | ucup-team987# | RE | 1ms | 3588kb | C++20 | 6.4kb | 2023-11-06 02:16:36 | 2023-11-06 02:16:36 |
Judging History
answer
#include<iostream>
#include<cassert>
using namespace std;
#include<iostream>
#include<algorithm>
#include<vector>
using Int=long long;
int sign(Int a){return a>0?1:a<0?-1:0;}
Int sqr(Int a){return a*a;}
struct Rational{
Int a,b;
Rational(Int a_=0):a(a_),b(1){}
Rational(Int a_,Int b_){
Int g=a_,h=b_;
while(h){
Int t=g%h;
g=h;
h=t;
}
a=a_/g;
b=b_/g;
if(b<0)a=-a,b=-b;
}
bool operator<(const Rational&r)const{return a*r.b<r.a*b;}
bool operator==(const Rational&r)const{return a==r.a&&b==r.b;}
};
struct Point{
Int x,y;
Point(Int x_=0,Int y_=0):x(x_),y(y_){}
Point operator-()const{return Point(-x,-y);}
Point operator+(const Point&p)const{return Point(x+p.x,y+p.y);}
Point operator-(const Point&p)const{return Point(x-p.x,y-p.y);}
Point operator*(const Int k)const{return Point(x*k,y*k);}
bool operator<(const Point&p)const{return x==p.x?y<p.y:x<p.x;}
bool operator==(const Point&p)const{return x==p.x&&y==p.y;}
};
istream&operator>>(istream&is,Point&p){return is>>p.x>>p.y;}
ostream&operator<<(ostream&os,const Point&p){return os<<p.x<<' '<<p.y;}
struct Line{
Point p1,p2;
Line(Point p1_=Point(),Point p2_=Point()):p1(p1_),p2(p2_){}
};
struct Segment:Line{
Segment(Point p1_=Point(),Point p2_=Point()):Line(p1_,p2_){}
};
struct Circle{
Point o;
Int r;
Circle(Point o_=Point(),Int r_=0):o(o_),r(r_){}
};
using Polygon=vector<Point>;
//function list begin
Point vec(const Line&);
Int norm(const Point&);
Int norm(const Line&);
int argtype(const Point&);//(-pi,0]->-1,(0,pi]->1,(0,0)->0
bool argless(const Point&,const Point&);//sorting points with arg
Int dot(const Point&,const Point&);
Int cross(const Point&,const Point&);
enum{ONLINE_FRONT=-2,CLOCKWISE=-1,ON_SEGMENT=0,COUNTER_CLOCKWISE=1,ONLINE_BACK=2};
int ccw(const Point&,const Point&);
int ccw(const Point&,const Point&,const Point&);
int ccw(const Line&,const Point&);
bool orthogonal(const Point&,const Point&);
bool orthogonal(const Line&,const Line&);
bool parallel(const Point&,const Point&);
bool parallel(const Line&,const Line&);
bool intersect(const Line&,const Point&);
bool intersect(const Line&,const Line&);
bool intersect(const Segment&,const Point&);
bool intersect(const Segment&,const Segment&);
bool intersect(const Line&,const Segment&);
bool intersect(const Segment&,const Line&);
bool intersect(const Circle&,const Point&);
int intersect(const Circle&,const Line&);//overflow, count contacts
int intersect(const Circle&,const Segment&);//overflow, count contacts
bool intersect(const Circle&,const Circle&);
int count_tangent(const Circle&,const Circle&);//count common tangents
Int distance2(const Point&,const Point&);
Rational distance2(const Line&,const Point&);
Rational distance2(const Line&,const Line&);
Rational distance2(const Segment&,const Point&);
Rational distance2(const Segment&,const Segment&);
Rational distance2(const Line&,const Segment&);
Rational distance2(const Segment&,const Line&);
bool is_convex(const Polygon&);
Polygon convex_hull(Polygon,bool=false);
enum{OUT,ON,IN};
int contain(const Polygon&,const Point&);
int contain(const Circle&,const Point&);
int contain(const Circle&,const Segment&);
int convex_contain(const Polygon&,const Point&);//O(log |P|)
Int diameter2(Polygon P);
//function list end
Point vec(const Line&s){return s.p2-s.p1;}
Int norm(const Point&p){return p.x*p.x+p.y*p.y;}
Int norm(const Line&s){return norm(vec(s));}
Int dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;}
Int cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
int ccw(const Point&a,const Point&b)
{
Int crs=cross(a,b);
return crs>0?COUNTER_CLOCKWISE
:crs<0?CLOCKWISE
:dot(a,b)<0?ONLINE_BACK
:norm(a)<norm(b)?ONLINE_FRONT
:ON_SEGMENT;
}
int ccw(const Point&a,const Point&b,const Point&c){return ccw(b-a,c-a);}
int ccw(const Line&s,const Point&p){return ccw(s.p1,s.p2,p);}
bool intersect(const Segment&s,const Segment&t){
return ccw(s,t.p1)*ccw(s,t.p2)<=0&&ccw(t,s.p1)*ccw(t,s.p2)<=0;
}
int N;
int X[50],Y[50],A[50],K[50];
const int a=10000,b=1;
vector<Point>L[50];
int up(int x)
{
while((x%a+a)%a!=a/2)x++;
return x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N;
int maxa=0;
for(int i=0;i<N;i++)
{
cin>>X[i]>>Y[i]>>A[i];
maxa=max(maxa,A[i]);
K[i]=a*X[i]+Y[i];
}
vector<int>k(K,K+N);
sort(k.begin(),k.end());
vector<int>mid;
mid.reserve(N+1);
mid.push_back(k[0]-1);
for(int i=1;i<N;i++)assert(k[i-1]+1<k[i]);
for(int i=0;i<N;i++)
{
mid.push_back(k[i]+1);
}
for(int i=0;i<mid.size();i++)
{
for(int x=0;x<maxa;x++)
{
//a*X+Y==mid[i]
int X=x+2000;
int Y=mid[i]-a*X;
L[x].push_back(Point(X,Y));
}
if(i<k.size())
{
int id=0;
while(K[id]!=k[i])id++;
for(int x=0;x<A[id];x++)
{
L[x].push_back(Point(X[id],Y[id]));
}
}
}
if(false)
{//check
for(int i=0;i<N;i++)
{
int cnt=0;
for(int j=0;j<maxa;j++)
{
bool fn=false;
for(Point p:L[j])if(p==Point(X[i],Y[i]))fn=true;
if(fn)cnt++;
}
assert(cnt==A[i]);
}
for(int i=0;i<maxa;i++)
{
assert(L[i].size()>=2);
for(int j=0;j<L[i].size();j++)
{
assert(abs(L[i][j].x)<=(int)1e9);
assert(abs(L[i][j].y)<=(int)1e9);
}
for(int j=0;j+1<L[i].size();j++)
{
Segment s(L[i][j],L[i][j+1]);
for(int k=0;k+1<L[i].size();k++)
{
if(abs(j-k)<=1)continue;
Segment t(L[i][k],L[i][k+1]);
if(intersect(s,t))
{
Point p;
int c=0;
if(s.p1==t.p1)p=s.p1,c++;
if(s.p1==t.p2)p=s.p1,c++;
if(s.p2==t.p1)p=s.p2,c++;
if(s.p2==t.p2)p=s.p2,c++;
assert(c==1);
bool fn=false;
for(int i=0;i<N;i++)if(p==Point(X[i],Y[i]))fn=true;
assert(fn);
}
}
for(int k=0;k<maxa;k++)if(k!=i)
{
for(int l=0;l+1<L[k].size();l++)
{
Segment t(L[k][l],L[k][l+1]);
if(intersect(s,t))
{
Point p;
int c=0;
if(s.p1==t.p1)p=s.p1,c++;
if(s.p1==t.p2)p=s.p1,c++;
if(s.p2==t.p1)p=s.p2,c++;
if(s.p2==t.p2)p=s.p2,c++;
assert(c==1);
bool fn=false;
for(int i=0;i<N;i++)if(p==Point(X[i],Y[i]))fn=true;
assert(fn);
}
}
}
}
}
}
cout<<maxa<<"\n";
for(int i=0;i<maxa;i++)
{
cout<<L[i].size();
for(Point p:L[i])cout<<" "<<p.x<<" "<<p.y;
cout<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3508kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 7 2000 -19989999 1 2 2000 -19989997 2 1 2000 -19979998 3 3 2000 -19969996 6 2001 -19999999 2001 -19999997 2 1 2001 -19989998 3 3 2001 -19979996
result:
ok ok Sum L = 13
Test #2:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
1 1 1 1
output:
1 3 2000 -19990000 1 1 2000 -19989998
result:
ok ok Sum L = 3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
1 1 1 50
output:
50 3 2000 -19990000 1 1 2000 -19989998 3 2001 -20000000 1 1 2001 -19999998 3 2002 -20010000 1 1 2002 -20009998 3 2003 -20020000 1 1 2003 -20019998 3 2004 -20030000 1 1 2004 -20029998 3 2005 -20040000 1 1 2005 -20039998 3 2006 -20050000 1 1 2006 -20049998 3 2007 -20060000 1 1 2007 -20059998 3 2008 -2...
result:
ok ok Sum L = 150
Test #4:
score: 0
Accepted
time: 1ms
memory: 3548kb
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 101 2000 -29810194 -981 -193 2000 -29810192 -945 382 2000 -29449617 -926 671 2000 -29259328 -888 -667 2000 -28880666 -885 -775 2000 -28850774 -870 -697 2000 -28700696 -825 381 2000 -28249618 -784 -537 2000 -27840536 -683 731 2000 -26829268 -668 -725 2000 -26680724 -579 -437 2000 -25790436 -558 82...
result:
ok ok Sum L = 3743
Test #5:
score: 0
Accepted
time: 0ms
memory: 3408kb
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 101 2000 -27719304 -772 697 2000 -27719302 -756 -909 2000 -27560908 -680 -67 2000 -26800066 -666 -82 2000 -26660081 -658 -229 2000 -26580228 -595 -470 2000 -25950469 -575 393 2000 -25749606 -573 613 2000 -25729386 -571 -716 2000 -25710715 -532 838 2000 -25319161 -530 890 2000 -25299109 -466 197 20...
result:
ok ok Sum L = 101
Test #6:
score: 0
Accepted
time: 1ms
memory: 3456kb
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 101 2000 -29989671 -999 330 2000 -29989669 -973 100 2000 -29729899 -962 -540 2000 -29620539 -888 -613 2000 -28880612 -842 381 2000 -28419618 -792 -625 2000 -27920624 -637 -801 2000 -26370800 -615 -675 2000 -26150674 -561 -302 2000 -25610301 -552 -966 2000 -25520965 -544 -51 2000 -25440050 -483 256...
result:
ok ok Sum L = 396
Test #7:
score: 0
Accepted
time: 1ms
memory: 3464kb
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 101 2000 -29820213 -982 -212 2000 -29820211 -980 753 2000 -29799246 -972 -312 2000 -29720311 -893 -204 2000 -28930203 -813 -921 2000 -28130920 -805 -304 2000 -28050303 -767 -974 2000 -27670973 -747 816 2000 -27469183 -660 -335 2000 -26600334 -647 161 2000 -26469838 -627 605 2000 -26269394 -560 -7...
result:
ok ok Sum L = 791
Test #8:
score: 0
Accepted
time: 1ms
memory: 3524kb
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 101 2000 -29979658 -998 343 2000 -29979656 -958 -511 2000 -29580510 -912 466 2000 -29119533 -887 151 2000 -28869848 -868 -114 2000 -28680113 -786 -384 2000 -27860383 -749 -631 2000 -27490630 -737 94 2000 -27369905 -649 -479 2000 -26490478 -615 809 2000 -26149190 -588 -138 2000 -25880137 -515 -540...
result:
ok ok Sum L = 4818
Test #9:
score: 0
Accepted
time: 1ms
memory: 3588kb
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 101 2000 -28820603 -882 -602 2000 -28820601 -851 279 2000 -28509720 -846 729 2000 -28459270 -841 601 2000 -28409398 -604 -168 2000 -26040167 -571 104 2000 -25709895 -544 307 2000 -25439692 -515 975 2000 -25149024 -501 927 2000 -25009072 -474 780 2000 -24739219 -369 -98 2000 -23690097 -367 -951 20...
result:
ok ok Sum L = 5050
Test #10:
score: -100
Runtime Error
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...