QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#307531 | #7680. Subway | mshcherba | AC ✓ | 1ms | 3876kb | C++20 | 2.9kb | 2024-01-18 19:43:27 | 2024-01-18 19:43:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
struct Pt
{
int x, y;
Pt operator+ (const Pt& p) const
{
return {x + p.x, y + p.y};
}
Pt operator- (const Pt& p) const
{
return {x - p.x, y - p.y};
}
Pt operator* (int d) const
{
return {x * d, y * d};
}
};
int sgn(LL x)
{
return (0 < x) - (x < 0);
}
LL cross(const Pt& p, const Pt& q)
{
return (LL)p.x * q.y - (LL)p.y * q.x;
}
LL orient(Pt p, Pt q, Pt r)
{
return cross(q - p, r - p);
}
bool properInter(const Pt& a, const Pt& b, const Pt& c, const Pt& d)
{
LL oa = orient(c, d, a);
LL ob = orient(c, d, b);
LL oc = orient(a, b, c);
LL od = orient(a, b, d);
return sgn(oa) * sgn(ob) == -1
&& sgn(oc) * sgn(od) == -1;
}
LL divFloor(LL a, LL b)
{
assert(b != 0);
if (b < 0)
{
a *= -1;
b *= -1;
}
a--;
LL res = a / b;
if (b * res > a)
res--;
assert(b * res <= a && b * (res + 1) > a);
return res;
}
int getX(const Pt& p1, const Pt& p2, LL y)
{
LL res = divFloor((y - p1.y) * (p2.x - p1.x), p2.y - p1.y) + p1.x;
assert(abs(res) <= 1e9);
return res;
}
db getXDB(const Pt& p1, const Pt& p2, LL y)
{
return (db)(y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
}
mt19937 rng;
int rand(int a, int b)
{
return a + rng() % (b - a);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<Pt> p(n);
VI a(n);
FOR(i, 0, n)
cin >> p[i].x >> p[i].y >> a[i];
if (n == 1)
{
n++;
p.PB({p[0].x + 4, p[0].y});
a.PB(1);
}
VI sortedIndices(n);
iota(ALL(sortedIndices), 0);
Pt p0;
while (true)
{
p0 = {rand(-1000, 1000), rand(2000, 2100)};
sort(ALL(sortedIndices), [&](int i, int j)
{
return orient(p0, p[i], p[j]) > 0;
});
bool ok = true;
FOR(i, 0, n - 1)
{
int j1 = sortedIndices[i], j2 = sortedIndices[i + 1];
ok &= orient(p0, p[j1], p[j2]) > 0;
}
if (ok)
break;
}
vector<vector<Pt>> ans(1);
for (int i : sortedIndices)
{
ans.back().PB(p[i]);
a[i]--;
}
for (int k = 1; *max_element(ALL(a)) > 0; k++)
{
ans.PB({});
FOR(i, 0, 2 * n - 1)
{
if (i % 2 == 0)
{
int j = sortedIndices[i / 2];
if (a[j] > 0)
{
a[j]--;
ans.back().PB(p[j]);
}
}
else
{
int j1 = sortedIndices[i / 2], j2 = sortedIndices[i / 2 + 1];
ans.back().PB(p0 * (1 - 2 * k) + (p[j1] + p[j2]) * k);
}
}
}
cout << SZ(ans) << "\n";
for (const auto& line : ans)
{
cout << SZ(line);
for (const auto& [x, y] : line)
cout << " " << x << " " << y;
cout << "\n";
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 3 1 2 2 1 3 3 4 -609 -1999 2 1 -607 -1998 3 3
result:
ok ok Sum L = 7
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1 1 1 1
output:
1 2 1 1 5 1
result:
ok ok Sum L = 2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 1 1 50
output:
50 2 1 1 5 1 2 1 1 -606 -2000 2 1 1 -1824 -6002 2 1 1 -3042 -10004 2 1 1 -4260 -14006 2 1 1 -5478 -18008 2 1 1 -6696 -22010 2 1 1 -7914 -26012 2 1 1 -9132 -30014 2 1 1 -10350 -34016 2 1 1 -11568 -38018 2 1 1 -12786 -42020 2 1 1 -14004 -46022 2 1 1 -15222 -50024 2 1 1 -16440 -54026 2 1 1 -17658 -5802...
result:
ok ok Sum L = 100
Test #4:
score: 0
Accepted
time: 1ms
memory: 3656kb
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 50 -926 671 -683 731 -558 825 -945 382 -825 381 -981 -193 -449 456 -182 810 -888 -667 -784 -537 -870 -697 -885 -775 -331 176 -499 -177 -579 -437 -469 -256 -668 -725 -548 -652 -141 226 -81 261 -205 -65 -462 -719 190 864 -106 59 -49 112 -371 -812 -306 -897 100 242 -3 -296 307 669 213 187 135 -187 4...
result:
ok ok Sum L = 3594
Test #5:
score: 0
Accepted
time: 1ms
memory: 3536kb
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 50 -772 697 -530 890 -532 838 -573 613 -304 897 -389 708 -575 393 -254 815 -187 841 -680 -67 -346 458 -666 -82 -466 197 -658 -229 -93 571 -595 -470 -66 573 -756 -909 -571 -716 175 846 133 685 103 546 -273 -672 277 928 -216 -711 69 190 -135 -509 -197 -795 -192 -890 -162 -959 223 400 179 157 115 -23...
result:
ok ok Sum L = 50
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
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 50 -999 330 -842 381 -973 100 -104 972 -293 667 -483 256 -962 -540 -888 -613 -544 -51 -472 44 -159 609 -792 -625 -364 169 -56 747 -561 -302 -615 -675 -637 -801 -47 393 -552 -966 -298 -330 -334 -535 -233 -432 24 -33 -29 -392 17 -757 345 628 348 -975 356 -986 457 -29 481 -91 564 186 594 -847 618 -91...
result:
ok ok Sum L = 337
Test #7:
score: 0
Accepted
time: 1ms
memory: 3772kb
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 50 -980 753 -747 816 -627 605 -324 816 -982 -212 -419 564 -972 -312 -647 161 -893 -204 -805 -304 -99 819 -215 624 -660 -335 -813 -921 -767 -974 -498 -458 -349 -163 -560 -748 -397 -741 101 576 -278 -598 -325 -875 274 948 -313 -996 -285 -980 9 -24 -258 -938 -189 -728 -48 -721 136 -54 119 -140 -19 -...
result:
ok ok Sum L = 722
Test #8:
score: 0
Accepted
time: 1ms
memory: 3676kb
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 50 -615 809 -912 466 -998 343 -486 866 -887 151 -195 889 -737 94 -868 -114 -308 652 -494 357 -958 -511 -786 -384 -588 -138 -127 643 -749 -631 -649 -479 -289 68 -367 -178 -515 -540 -268 -39 -212 26 25 524 -287 -285 210 944 134 661 -142 -167 59 363 151 574 -55 -114 117 418 -282 -917 -14 -257 98 -79...
result:
ok ok Sum L = 4669
Test #9:
score: 0
Accepted
time: 1ms
memory: 3876kb
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 50 -846 729 -515 975 -841 601 -501 927 -474 780 -851 279 -544 307 -571 104 -324 450 -882 -602 -604 -168 -335 56 -2 713 -369 -98 21 679 50 646 -143 56 -193 -370 -367 -951 -80 -172 -302 -989 262 792 -126 -799 253 550 168 180 27 -476 128 -265 151 -171 149 -378 263 119 150 -618 308 229 294 -70 197 -9...
result:
ok ok Sum L = 4901
Test #10:
score: 0
Accepted
time: 1ms
memory: 3548kb
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 50 -5 1 -5 0 -3 5 -4 1 -5 -3 -3 3 -5 -4 -2 5 -3 1 -4 -3 -3 0 -4 -4 -3 -1 -2 2 -1 5 -3 -2 -1 4 -3 -3 -1 3 -2 -1 0 5 0 3 1 5 -2 -5 0 0 -1 -4 0 -1 0 -2 2 4 0 -3 0 -4 1 -1 2 2 3 5 0 -5 1 -2 1 -4 2 -1 4 5 1 -5 4 4 2 -3 2 -5 3 -2 4 -1 5 2 5 1 5 0 5 -1 5 -4 99 -5 1 -622 -2001 -5 0 -620 -1997 -3 5 -619 -...
result:
ok ok Sum L = 3825
Test #11:
score: 0
Accepted
time: 1ms
memory: 3768kb
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 50 -5 5 -4 5 -5 1 -4 4 -5 -1 -3 5 -4 1 -5 -3 -3 2 -2 5 -5 -5 -2 4 -3 0 -4 -4 -2 2 -3 -2 -2 1 -3 -3 -3 -4 -2 -1 -1 2 -2 -2 -2 -4 -1 -2 -1 -4 0 -1 2 5 0 -2 1 1 2 3 2 2 3 5 1 -2 2 0 1 -4 2 -1 2 -2 4 4 2 -3 2 -4 4 2 5 5 3 -2 4 1 3 -3 5 3 3 -5 5 0 5 -1 5 -5 85 -5 5 -621 -1992 -4 5 -621 -1996 -5 1 -621 ...
result:
ok ok Sum L = 135
Test #12:
score: 0
Accepted
time: 1ms
memory: 3596kb
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 50 -5 5 -5 4 -4 4 -5 -1 -3 5 -4 1 -5 -3 -5 -5 -2 3 -3 -1 -1 5 -4 -5 -2 0 -3 -4 0 5 -3 -5 -1 1 0 4 -2 -3 -1 0 -2 -4 -1 -1 0 2 -1 -2 1 4 -1 -4 0 -1 1 2 -1 -5 0 -2 0 -3 0 -4 3 5 1 -2 1 -3 2 0 1 -4 3 2 1 -5 4 3 3 -1 4 2 2 -5 5 4 3 -3 4 0 4 -3 4 -4 5 -1 5 -3 99 -5 5 -622 -1993 -5 4 -621 -1994 -4 4 -62...
result:
ok ok Sum L = 4878
Test #13:
score: 0
Accepted
time: 0ms
memory: 3864kb
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 50 114 514 115 514 116 514 117 514 118 514 119 514 120 514 121 514 122 514 123 514 124 514 125 514 126 514 127 514 128 514 129 514 130 514 131 514 132 514 133 514 134 514 135 514 136 514 137 514 138 514 139 514 140 514 141 514 142 514 143 514 144 514 145 514 146 514 147 514 148 514 149 514 150 51...
result:
ok ok Sum L = 3504
Test #14:
score: 0
Accepted
time: 1ms
memory: 3636kb
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 50 191 981 191 980 191 979 191 978 191 977 191 976 191 975 191 974 191 973 191 972 191 971 191 970 191 969 191 968 191 967 191 966 191 965 191 964 191 963 191 962 191 961 191 960 191 959 191 958 191 957 191 956 191 955 191 954 191 953 191 952 191 951 191 950 191 949 191 948 191 947 191 946 191 94...
result:
ok ok Sum L = 3504
Test #15:
score: 0
Accepted
time: 1ms
memory: 3604kb
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 50 -123 456 -122 457 -121 458 -120 459 -119 460 -118 461 -117 462 -116 463 -115 464 -114 465 -113 466 -112 467 -111 468 -110 469 -109 470 -108 471 -107 472 -106 473 -105 474 -104 475 -103 476 -102 477 -101 478 -100 479 -99 480 -98 481 -97 482 -96 483 -95 484 -94 485 -93 486 -92 487 -91 488 -90 48...
result:
ok ok Sum L = 3607
Test #16:
score: 0
Accepted
time: 1ms
memory: 3664kb
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 50 321 -525 322 -526 323 -527 324 -528 325 -529 326 -530 327 -531 328 -532 329 -533 330 -534 331 -535 332 -536 333 -537 334 -538 335 -539 336 -540 337 -541 338 -542 339 -543 340 -544 341 -545 342 -546 343 -547 344 -548 345 -549 346 -550 347 -551 348 -552 349 -553 350 -554 351 -555 352 -556 353 -5...
result:
ok ok Sum L = 3613
Test #17:
score: 0
Accepted
time: 1ms
memory: 3580kb
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 50 -493 -604 -492 -603 -491 -602 -490 -601 -489 -600 -488 -599 -487 -598 -486 -597 -485 -596 -484 -595 -483 -594 -482 -593 -481 -592 -480 -591 -479 -590 -478 -589 -477 -588 -476 -587 -475 -586 -474 -585 -473 -584 -472 -583 -471 -582 -470 -581 -469 -580 -468 -579 -467 -578 -466 -577 -465 -576 -464...
result:
ok ok Sum L = 3562
Test #18:
score: 0
Accepted
time: 1ms
memory: 3648kb
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 50 -191 49 -190 48 -189 47 -188 46 -187 45 -186 44 -185 43 -184 42 -183 41 -182 40 -181 39 -180 38 -179 37 -178 36 -177 35 -176 34 -175 33 -174 32 -173 31 -172 30 -171 29 -170 28 -169 27 -168 26 -167 25 -166 24 -165 23 -164 22 -163 21 -162 20 -161 19 -160 18 -159 17 -158 16 -157 15 -156 14 -155 1...
result:
ok ok Sum L = 3712
Test #19:
score: 0
Accepted
time: 0ms
memory: 3552kb
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 12 -1000 1000 -999 1000 -1000 999 -1000 -999 -1000 -1000 -999 -1000 999 -1000 1000 -1000 1000 -999 999 1000 1000 999 1000 1000 23 -1000 1000 -2611 -2 -999 1000 -2611 -3 -1000 999 -2612 -2002 -1000 -999 -2612 -4001 -1000 -1000 -2611 -4002 -999 -1000 -612 -4002 999 -1000 1387 -4002 1000 -1000 1388 ...
result:
ok ok Sum L = 1139
Test #20:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
4 1000 1000 50 1000 -1000 50 -1000 1000 50 -1000 -1000 50
output:
50 4 -1000 1000 -1000 -1000 1000 -1000 1000 1000 7 -1000 1000 -2612 -2002 -1000 -1000 -612 -4002 1000 -1000 1388 -2002 1000 1000 7 -1000 1000 -5836 -6006 -1000 -1000 -1836 -10006 1000 -1000 2164 -6006 1000 1000 7 -1000 1000 -9060 -10010 -1000 -1000 -3060 -16010 1000 -1000 2940 -10010 1000 1000 7 -10...
result:
ok ok Sum L = 347
Extra Test:
score: 0
Extra Test Passed