QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#238378#7680. Subwayucup-team266#WA 1ms3688kbC++143.5kb2023-11-04 16:33:452023-11-04 16:33:45

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 16:33:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3688kb
  • [2023-11-04 16:33:45]
  • 提交

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.