QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246917 | #7680. Subway | ucup-team052# | AC ✓ | 1ms | 4076kb | C++14 | 2.3kb | 2023-11-11 12:12:13 | 2023-11-11 12:12:14 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=55;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(0);
int brand(){return rng()&0X7FFFFFFF;}
int n,cur[N];
struct vec{
int x,y,tt;
vec operator-(const vec&rhs)const{return (vec){x-rhs.x,y-rhs.y,0};}
vec operator+(const vec&rhs)const{return (vec){x+rhs.x,y+rhs.y,0};}
vec operator*(const int&k)const{return (vec){x*k,y*k,0};}
}a[N],w[N];
LL cross(vec a,vec b){return 1LL*a.x*b.y-1LL*a.y*b.x;}
vec Get(vec a,vec b){
return a+b;
}
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
rd(n);
int ans=0;
rep(i,1,n){
rd(a[i].x),rd(a[i].y),rd(a[i].tt);
ans=max(ans,a[i].tt);
}
if(n==1){
printf("%d\n",ans);
rep(i,1,ans){
printf("2 %d %d %d %d\n",a[1].x,a[1].y,a[1].x+1,a[1].y+i);
}
return 0;
}
vec bg;
auto test=[&](){
rep(i,1,n){
rep(j,i+1,n){
if(cross(a[i]-bg,a[j]-bg)==0){
return 0;
}
}
}
return 1;
};
while(1){
bg=(vec){-1001-brand()%1000,-1001-brand()%1000};
if(test())break;
}
sort(a+1,a+n+1,[&](vec a,vec b){return cross(a-bg,b-bg)>0;});
rep(i,1,n-1){
w[i]=Get(a[i]-bg,a[i+1]-bg);
}
rep(i,1,n){
cur[i]=0;
}
printf("%d\n",ans);
rep(_,1,ans){
vector<vec>v;
rep(i,1,n){
if(a[i].tt){
--a[i].tt;
v.pb(a[i]);
}else{
++cur[i];
v.pb(a[i]+(a[i]-bg)*cur[i]);
}
if(i<n){
v.pb(bg+w[i]*_);
}
}
printf("%d ",SZ(v));
for(auto&[x,y,z]:v)printf("%d %d ",x,y);
puts("");
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3996kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 5 2 1 1402 1596 3 3 1401 1597 1 2 5 2 1 4201 4784 3 3 4199 4786 1399 1596
result:
ok ok Sum L = 10
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 1 1 1
output:
1 2 1 1 2 2
result:
ok ok Sum L = 2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
1 1 1 50
output:
50 2 1 1 2 2 2 1 1 2 3 2 1 1 2 4 2 1 1 2 5 2 1 1 2 6 2 1 1 2 7 2 1 1 2 8 2 1 1 2 9 2 1 1 2 10 2 1 1 2 11 2 1 1 2 12 2 1 1 2 13 2 1 1 2 14 2 1 1 2 15 2 1 1 2 16 2 1 1 2 17 2 1 1 2 18 2 1 1 2 19 2 1 1 2 20 2 1 1 2 21 2 1 1 2 22 2 1 1 2 23 2 1 1 2 24 2 1 1 2 25 2 1 1 2 26 2 1 1 2 27 2 1 1 2 28 2 1 1 2 ...
result:
ok ok Sum L = 100
Test #4:
score: 0
Accepted
time: 1ms
memory: 3708kb
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 961 -919 2692 -220 334 -893 2467 148 736 -551 2795 474 662 -567 2261 323 202 -702 1293 -7 -306 -897 1937 532 846 -163 2860 1124 617 -305 2899 1230 885 -57 3010 1415 728 -120 2473 1150 348 -322 2251 1095 506 -175 1532 605 -371 -812 1966 978 940 198 3190 2035 853 245 2867 2045 617 208 2149 1613 ...
result:
ok ok Sum L = 4950
Test #5:
score: 0
Accepted
time: 0ms
memory: 3696kb
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 749 -723 2176 0 30 -869 1900 84 473 -639 1708 -6 -162 -959 1595 3 360 -630 2090 325 333 -637 1538 65 -192 -890 2103 530 898 -172 2098 625 -197 -795 1929 682 729 -115 1910 766 -216 -711 2092 1156 911 275 2035 1195 -273 -672 989 411 -135 -509 1767 1151 505 68 2017 1425 115 -235 1726 1219 214 -138...
result:
ok ok Sum L = 99
Test #6:
score: 0
Accepted
time: 0ms
memory: 3780kb
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 846 -893 2861 -212 618 -911 2371 -305 356 -986 2624 -193 871 -799 2616 -182 348 -975 2339 -230 594 -847 2665 -59 674 -804 2911 150 840 -638 3230 464 993 -490 3177 604 787 -498 3122 743 938 -351 3180 858 845 -383 2259 452 17 -757 2344 696 930 -139 3112 1264 785 -189 3075 1370 893 -33 1738 593 -5...
result:
ok ok Sum L = 495
Test #7:
score: 0
Accepted
time: 1ms
memory: 3808kb
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 932 -941 3082 171 753 -480 2316 346 166 -766 1832 121 269 -705 1647 42 -19 -845 1065 -249 -313 -996 1410 -48 326 -644 1438 -32 -285 -980 854 -326 -258 -938 1091 -67 -48 -721 1024 -4 -325 -875 1159 135 87 -582 2408 1078 924 68 2132 932 -189 -728 1268 363 60 -501 2454 1376 997 285 1997 1136 -397...
result:
ok ok Sum L = 990
Test #8:
score: 0
Accepted
time: 1ms
memory: 4000kb
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 808 -695 3143 301 938 -596 2410 38 75 -958 1745 -196 273 -830 1843 -95 173 -857 2107 98 537 -637 1958 66 24 -889 2401 287 980 -416 2908 727 531 -449 1646 226 -282 -917 1560 231 445 -444 1981 698 139 -450 2417 1300 881 158 2475 1478 197 -272 1580 1063 -14 -257 1484 1201 101 -134 1596 1379 98 -7...
result:
ok ok Sum L = 4950
Test #9:
score: 0
Accepted
time: 1ms
memory: 3708kb
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 417 -944 2081 -317 267 -965 2145 -246 481 -873 2791 19 913 -700 2953 113 643 -779 2237 -110 197 -923 2489 105 895 -564 2790 392 498 -636 1593 -33 -302 -989 2040 353 945 -250 2891 886 549 -456 2866 899 920 -237 2738 892 421 -463 1451 178 -367 -951 904 -158 -126 -799 1421 175 150 -618 1574 498 2...
result:
ok ok Sum L = 4950
Test #10:
score: 0
Accepted
time: 1ms
memory: 3736kb
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 1404 1583 2 -5 1404 1586 5 -1 1403 1586 1 -5 1403 1587 5 0 1406 1591 4 -1 1404 1589 3 -2 1402 1587 2 -3 1400 1585 1 -4 1398 1583 0 -5 1402 1588 5 1 1402 1589 0 -4 1402 1590 5 2 1404 1593 2 -1 1400 1589 1 -2 1398 1587 0 -3 1396 1585 -1 -4 1394 1583 -2 -5 1396 1586 1 -1 1398 1589 0 -2 1397 ...
result:
ok ok Sum L = 4950
Test #11:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
50 2 0 2 2 -3 2 4 1 2 -3 -3 2 -5 1 2 5 3 2 -5 -3 2 -3 -2 2 2 -1 2 2 3 2 4 4 1 1 -4 1 5 -1 2 -4 1 2 3 -2 1 -1 2 2 5 -5 2 -2 1 2 -5 -1 2 -2 -1 2 -1 -2 2 5 5 1 0 -2 2 1 1 1 2 2 2 3 5 2 -2 -4 1 -3 5 1 4 2 2 -4 -4 2 -3 2 1 5 0 2 -2 -2 2 -4 4 1 -2 5 2 2 5 1 3 -5 2 -4 5 2 -5 5 2 -2 4 2 -5 -5 2 -2 2 2 -3 -4...
output:
2 99 5 -5 1405 1582 3 -5 1405 1586 5 -1 1405 1588 3 -3 1402 1585 2 -4 1404 1588 5 0 1405 1590 3 -2 1402 1587 2 -3 1400 1585 1 -4 1400 1586 2 -2 1403 1591 4 1 1403 1592 2 -1 1400 1589 1 -2 1397 1586 -1 -4 1401 1591 5 3 1406 1597 4 2 1403 1594 2 0 1399 1590 0 -2 1395 1586 -2 -4 1395 1587 0 -1 1396 158...
result:
ok ok Sum L = 198
Test #12:
score: 0
Accepted
time: 1ms
memory: 4076kb
input:
50 4 3 49 -5 -3 49 0 -3 50 -2 -4 49 -5 -5 50 4 0 49 -1 -2 49 -2 0 49 1 2 50 -1 -5 50 -5 -1 50 -5 5 49 2 0 50 -2 -3 50 -4 -5 50 0 -2 50 -5 4 50 -1 1 49 -1 -4 49 -3 -1 49 1 -3 50 -4 1 50 0 5 50 1 -2 50 -1 5 50 4 2 50 4 -3 49 1 -4 49 -1 -1 49 -3 -5 50 4 -4 50 3 2 49 3 -3 49 0 2 50 -3 -4 49 5 -1 49 -3 5...
output:
50 99 5 -3 1406 1585 4 -4 1405 1585 4 -3 1403 1584 2 -5 1404 1586 5 -1 1405 1588 3 -3 1401 1584 1 -5 1399 1583 1 -4 1402 1588 4 0 1404 1591 3 -1 1401 1588 1 -3 1398 1585 0 -4 1396 1583 -1 -5 1397 1585 1 -2 1398 1587 0 -3 1396 1585 -1 -4 1400 1590 4 2 1403 1594 2 0 1399 1590 0 -2 1395 1586 -2 -4 1400...
result:
ok ok Sum L = 4950
Test #13:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
50 114 514 30 115 514 41 116 514 6 117 514 49 118 514 10 119 514 49 120 514 1 121 514 7 122 514 3 123 514 4 124 514 1 125 514 12 126 514 15 127 514 16 128 514 34 129 514 24 130 514 49 131 514 43 132 514 25 133 514 12 134 514 26 135 514 13 136 514 12 137 514 15 138 514 7 139 514 25 140 514 5 141 514 ...
output:
49 99 163 514 1722 2620 162 514 1720 2620 161 514 1718 2620 160 514 1716 2620 159 514 1714 2620 158 514 1712 2620 157 514 1710 2620 156 514 1708 2620 155 514 1706 2620 154 514 1704 2620 153 514 1702 2620 152 514 1700 2620 151 514 1698 2620 150 514 1696 2620 149 514 1694 2620 148 514 1692 2620 147 51...
result:
ok ok Sum L = 4851
Test #14:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
50 191 981 19 191 980 41 191 979 20 191 978 14 191 977 2 191 976 49 191 975 40 191 974 3 191 973 20 191 972 6 191 971 13 191 970 4 191 969 4 191 968 47 191 967 32 191 966 11 191 965 34 191 964 30 191 963 3 191 962 16 191 961 24 191 960 30 191 959 34 191 958 31 191 957 24 191 956 29 191 955 42 191 95...
output:
49 99 191 932 1779 3457 191 933 1779 3459 191 934 1779 3461 191 935 1779 3463 191 936 1779 3465 191 937 1779 3467 191 938 1779 3469 191 939 1779 3471 191 940 1779 3473 191 941 1779 3475 191 942 1779 3477 191 943 1779 3479 191 944 1779 3481 191 945 1779 3483 191 946 1779 3485 191 947 1779 3487 191 94...
result:
ok ok Sum L = 4851
Test #15:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
50 -123 456 47 -122 457 35 -121 458 25 -120 459 35 -119 460 30 -118 461 33 -117 462 21 -116 463 31 -115 464 21 -114 465 35 -113 466 20 -112 467 17 -111 468 25 -110 469 3 -109 470 29 -108 471 35 -107 472 4 -106 473 44 -105 474 4 -104 475 28 -103 476 49 -102 477 9 -101 478 39 -100 479 9 -99 480 21 -98...
output:
50 99 -74 505 1248 2601 -75 504 1246 2599 -76 503 1244 2597 -77 502 1242 2595 -78 501 1240 2593 -79 500 1238 2591 -80 499 1236 2589 -81 498 1234 2587 -82 497 1232 2585 -83 496 1230 2583 -84 495 1228 2581 -85 494 1226 2579 -86 493 1224 2577 -87 492 1222 2575 -88 491 1220 2573 -89 490 1218 2571 -90 48...
result:
ok ok Sum L = 4950
Test #16:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
50 321 -525 46 322 -526 14 323 -527 16 324 -528 38 325 -529 22 326 -530 24 327 -531 48 328 -532 5 329 -533 7 330 -534 30 331 -535 25 332 -536 2 333 -537 13 334 -538 1 335 -539 33 336 -540 8 337 -541 9 338 -542 2 339 -543 29 340 -544 17 341 -545 41 342 -546 39 343 -547 9 344 -548 47 345 -549 47 346 -...
output:
50 99 370 -574 2136 445 369 -573 2134 447 368 -572 2132 449 367 -571 2130 451 366 -570 2128 453 365 -569 2126 455 364 -568 2124 457 363 -567 2122 459 362 -566 2120 461 361 -565 2118 463 360 -564 2116 465 359 -563 2114 467 358 -562 2112 469 357 -561 2110 471 356 -560 2108 473 355 -559 2106 475 354 -5...
result:
ok ok Sum L = 4950
Test #17:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
50 -444 -555 23 -445 -556 32 -446 -557 36 -447 -558 29 -448 -559 4 -449 -560 25 -450 -561 29 -451 -562 5 -452 -563 9 -453 -564 28 -454 -565 35 -455 -566 26 -456 -567 22 -457 -568 39 -458 -569 13 -459 -570 50 -460 -571 37 -461 -572 14 -462 -573 26 -463 -574 49 -464 -575 23 -465 -576 44 -466 -577 2 -4...
output:
50 99 -444 -555 508 481 -445 -556 506 479 -446 -557 504 477 -447 -558 502 475 -448 -559 500 473 -449 -560 498 471 -450 -561 496 469 -451 -562 494 467 -452 -563 492 465 -453 -564 490 463 -454 -565 488 461 -455 -566 486 459 -456 -567 484 457 -457 -568 482 455 -458 -569 480 453 -459 -570 478 451 -460 -...
result:
ok ok Sum L = 4950
Test #18:
score: 0
Accepted
time: 1ms
memory: 4072kb
input:
50 -142 0 48 -143 1 22 -144 2 45 -145 3 9 -146 4 36 -147 5 46 -148 6 26 -149 7 26 -150 8 9 -151 9 19 -152 10 22 -153 11 14 -154 12 8 -155 13 20 -156 14 41 -157 15 47 -158 16 22 -159 17 50 -160 18 3 -161 19 12 -162 20 15 -163 21 32 -164 22 46 -165 23 45 -166 24 3 -167 25 27 -168 26 33 -169 27 17 -170...
output:
50 99 -142 0 1112 1593 -143 1 1110 1595 -144 2 1108 1597 -145 3 1106 1599 -146 4 1104 1601 -147 5 1102 1603 -148 6 1100 1605 -149 7 1098 1607 -150 8 1096 1609 -151 9 1094 1611 -152 10 1092 1613 -153 11 1090 1615 -154 12 1088 1617 -155 13 1086 1619 -156 14 1084 1621 -157 15 1082 1623 -158 16 1080 162...
result:
ok ok Sum L = 4950
Test #19:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
12 1000 1000 50 1000 -1000 50 1000 999 50 999 1000 50 999 -1000 50 -999 1000 50 1000 -999 50 -999 -1000 50 -1000 1000 50 -1000 -1000 50 -1000 -999 50 -1000 999 50
output:
50 23 1000 -1000 3396 -408 999 -1000 3396 -407 1000 -999 3397 1592 1000 999 3397 3591 1000 1000 3396 3592 999 1000 1397 1592 -999 -1000 -602 -408 -1000 -1000 -603 -407 -1000 -999 -602 1593 -999 1000 -602 3591 -1000 999 -603 3591 -1000 1000 23 1000 -1000 8189 776 999 -1000 8189 778 1000 -999 8191 47...
result:
ok ok Sum L = 1150
Test #20:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
4 1000 1000 50 1000 -1000 50 -1000 1000 50 -1000 -1000 50
output:
50 7 1000 -1000 3397 1592 1000 1000 1397 1592 -1000 -1000 -603 1592 -1000 1000 7 1000 -1000 8191 4776 1000 1000 4191 4776 -1000 -1000 191 4776 -1000 1000 7 1000 -1000 12985 7960 1000 1000 6985 7960 -1000 -1000 985 7960 -1000 1000 7 1000 -1000 17779 11144 1000 1000 9779 11144 -1000 -1000 1779 1114...
result:
ok ok Sum L = 350
Extra Test:
score: 0
Extra Test Passed