QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258419#7680. Subway8BQube#AC ✓1ms3580kbC++202.3kb2023-11-19 17:55:262023-11-19 17:55:27

Judging History

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

  • [2023-11-19 17:55:27]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3580kb
  • [2023-11-19 17:55:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

const int MAXC = 100;
const int CCC = 1e9;

pii arr[55], org[55];
int deg[55];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, ans;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].X >> arr[i].Y >> deg[i];
        org[i] = arr[i];
    }
    ans = *max_element(deg + 1, deg + n + 1);
    mt19937 rng(880301);

    int alpha, beta;

    auto transfer = [&](pii a) {
        return pii((1 + alpha * beta) * a.X + beta * a.Y, alpha * a.X + a.Y);  
    };

    auto inv = [&](pii a) {
        return pii(a.X - beta * a.Y, -alpha * a.X + (1 + alpha * beta) * a.Y);   
    };

    auto check = [&]() {
        vector<int> coord;
        for (int i = 1; i <= n; ++i)  {
            arr[i] = transfer(org[i]);
            coord.pb(arr[i].X);
        }
        sort(ALL(coord));
        for (int i = 0; i + 1 < SZ(coord); ++i)
            if (coord[i] + 1 >= coord[i + 1])
                return false;
        return true;
    };

    do {
        alpha = rng() % MAXC + 1;
        beta = rng() % MAXC + 1;
    } while (!check());
    
    assert(pii(1, 1) == inv(transfer(pii(1, 1))));
    
    vector<int> idx(n);
    iota(ALL(idx), 1);
    sort(ALL(idx), [&](int a, int b) {
        return arr[a].X < arr[b].X; 
    });

    vector<vector<pii>> output(ans);
    for (int i = 0; i < n; ++i) {
        int u = idx[i], x = arr[u].X;
        for (int j = 0; j < deg[u]; ++j)
            output[j].pb(pii(x, arr[u].Y));
        for (int j = deg[u]; j < ans; ++j)
            output[j].pb(pii(x, arr[u].Y + j + 1 - deg[u]));
        for (int j = 0; j < ans; ++j)
            output[j].pb(pii(x + 1, j));
    }
   
    cout << ans << "\n";
    for (int i = 0; i < ans; ++i) {
        cout << SZ(output[i]);
        for (pii p : output[i]) {
            p = inv(p);
            assert(abs(p.X) <= CCC && abs(p.Y) <= CCC);
            cout << " " << p.X << " " << p.Y;
        }
        cout << "\n";
    }
}
/*
3
1 2 1
2 1 2
3 3 2
2
6 1 2 164 -1148 2 1 273 -1911 3 3 436 -3052
6 -17 129 146 -1021 2 1 255 -1784 3 3 418 -2925
*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3424kb

input:

3
1 2 1
2 1 2
3 3 2

output:

2
6 1 2 164 -1148 2 1 273 -1911 3 3 436 -3052
6 -17 129 146 -1021 2 1 255 -1784 3 3 418 -2925

result:

ok ok Sum L = 12

Test #2:

score: 0
Accepted
time: 0ms
memory: 3372kb

input:

1
1 1 1

output:

1
2 1 1 146 -1022

result:

ok ok Sum L = 2

Test #3:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

1
1 1 50

output:

50
2 1 1 146 -1022
2 1 1 128 -895
2 1 1 110 -768
2 1 1 92 -641
2 1 1 74 -514
2 1 1 56 -387
2 1 1 38 -260
2 1 1 20 -133
2 1 1 2 -6
2 1 1 -16 121
2 1 1 -34 248
2 1 1 -52 375
2 1 1 -70 502
2 1 1 -88 629
2 1 1 -106 756
2 1 1 -124 883
2 1 1 -142 1010
2 1 1 -160 1137
2 1 1 -178 1264
2 1 1 -196 1391
2 1 1 ...

result:

ok ok Sum L = 100

Test #4:

score: 0
Accepted
time: 1ms
memory: 3460kb

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
100 -981 -193 -128060 896420 -885 -775 -126344 884408 -888 -667 -124781 873467 -870 -697 -123035 861245 -945 382 -113138 791966 -784 -537 -109233 764631 -926 671 -105523 738661 -825 381 -97916 685412 -668 -725 -97885 685195 -579 -437 -81398 569786 -548 -652 -81331 569317 -683 731 -73582 515074 -4...

result:

ok ok Sum L = 5000

Test #5:

score: 0
Accepted
time: 1ms
memory: 3404kb

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
100 -756 -909 -112373 786611 -658 -229 -87687 613809 -680 -67 -87565 612955 -666 -82 -86057 602399 -772 697 -85497 598479 -571 -716 -85404 597828 -595 -470 -84024 588168 -575 393 -65950 461650 -573 613 -61736 432152 -466 197 -55635 389445 -532 838 -52479 367353 -530 890 -51289 359023 -273 -672 -46...

result:

ok ok Sum L = 100

Test #6:

score: 0
Accepted
time: 1ms
memory: 3416kb

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
100 -962 -540 -131893 923251 -888 -613 -123809 866663 -973 100 -121770 852390 -999 330 -120932 846524 -792 -625 -111833 782831 -842 381 -100075 700525 -637 -801 -95316 667212 -615 -675 -90254 631778 -552 -966 -87491 612437 -561 -302 -76682 536774 -544 -51 -70005 490035 -472 44 -59151 414057 -483 2...

result:

ok ok Sum L = 500

Test #7:

score: 0
Accepted
time: 1ms
memory: 3404kb

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
100 -972 -312 -129059 903413 -982 -212 -128529 899703 -813 -921 -119828 838796 -893 -204 -117082 819574 -767 -974 -114940 804580 -980 753 -110905 776335 -805 -304 -107706 753942 -660 -335 -89849 628943 -560 -748 -84583 592081 -747 816 -80180 561260 -647 161 -79270 554890 -498 -458 -71489 500423 -...

result:

ok ok Sum L = 1000

Test #8:

score: 0
Accepted
time: 1ms
memory: 3456kb

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
100 -958 -511 -130863 916041 -998 343 -120571 843997 -868 -114 -112287 786009 -887 151 -109930 769510 -912 466 -107435 752045 -786 -384 -106733 747131 -749 -631 -106480 745360 -737 94 -91906 643342 -649 -479 -91044 637308 -588 -138 -77159 540113 -515 -540 -75124 525868 -615 809 -63542 444794 -494...

result:

ok ok Sum L = 5000

Test #9:

score: 0
Accepted
time: 1ms
memory: 3520kb

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
100 -882 -602 -122849 859943 -851 279 -103054 721378 -841 601 -95988 671916 -846 729 -94319 660233 -604 -168 -79731 558117 -571 104 -70644 494508 -367 -951 -63726 446082 -544 307 -63561 444927 -302 -989 -56155 393085 -369 -98 -48626 340382 -515 975 -47854 334978 -501 927 -46940 328580 -474 780 -4...

result:

ok ok Sum L = 5000

Test #10:

score: 0
Accepted
time: 1ms
memory: 3544kb

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
100 -5 -4 -16973 797731 -5 -3 -16902 794394 -5 0 -16689 784383 -5 1 -16618 781046 -4 -4 -13635 640845 -4 -3 -13564 637508 -4 1 -13280 624160 -3 -3 -10226 480622 -3 -2 -10155 477285 -3 -1 -10084 473948 -3 0 -10013 470611 -3 1 -9942 467274 -3 3 -9800 460600 -3 5 -9658 453926 -2 -5 -7030 330410 -2 -...

result:

ok ok Sum L = 5000

Test #11:

score: 0
Accepted
time: 1ms
memory: 3396kb

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
100 -5 -5 -17044 801068 -5 -3 -16902 794394 -5 -1 -16760 787720 -5 1 -16618 781046 -5 5 -16334 767698 -4 -4 -13635 640845 -4 1 -13280 624160 -4 4 -13067 614149 -4 5 -12996 610812 -3 -4 -10297 483959 -3 -3 -10226 480622 -3 -2 -10155 477285 -3 0 -10013 470611 -3 2 -9871 463937 -3 5 -9658 453926 -2 -...

result:

ok ok Sum L = 200

Test #12:

score: 0
Accepted
time: 1ms
memory: 3460kb

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
100 -5 -5 -17044 801068 -5 -3 -16902 794394 -5 -1 -16760 787720 -5 4 -16405 771035 -5 5 -16334 767698 -4 -5 -13706 644182 -4 1 -13280 624160 -4 4 -13067 614149 -3 -5 -10368 487296 -3 -4 -10297 483959 -3 -1 -10084 473948 -3 5 -9658 453926 -2 -4 -6959 327073 -2 -3 -6888 323736 -2 0 -6675 313725 -2 ...

result:

ok ok Sum L = 5000

Test #13:

score: 0
Accepted
time: 1ms
memory: 3560kb

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
100 114 514 23731 -166117 115 514 23858 -167006 116 514 23985 -167895 117 514 24112 -168784 118 514 24239 -169673 119 514 24366 -170562 120 514 24493 -171451 121 514 24620 -172340 122 514 24747 -173229 123 514 24874 -174118 124 514 25001 -175007 125 514 25128 -175896 126 514 25255 -176785 127 514...

result:

ok ok Sum L = 4900

Test #14:

score: 0
Accepted
time: 1ms
memory: 3528kb

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
100 191 932 41034 -287238 191 933 41052 -287364 191 934 41070 -287490 191 935 41088 -287616 191 936 41106 -287742 191 937 41124 -287868 191 938 41142 -287994 191 939 41160 -288120 191 940 41178 -288246 191 941 41196 -288372 191 942 41214 -288498 191 943 41232 -288624 191 944 41250 -288750 191 945...

result:

ok ok Sum L = 4900

Test #15:

score: 0
Accepted
time: 1ms
memory: 3464kb

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
100 -123 456 -7412 51884 -122 457 -7267 50869 -121 458 -7122 49854 -120 459 -6977 48839 -119 460 -6832 47824 -118 461 -6687 46809 -117 462 -6542 45794 -116 463 -6397 44779 -115 464 -6252 43764 -114 465 -6107 42749 -113 466 -5962 41734 -112 467 -5817 40719 -111 468 -5672 39704 -110 469 -5527 38689...

result:

ok ok Sum L = 5000

Test #16:

score: 0
Accepted
time: 1ms
memory: 3456kb

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
100 321 -525 31318 -219226 322 -526 31427 -219989 323 -527 31536 -220752 324 -528 31645 -221515 325 -529 31754 -222278 326 -530 31863 -223041 327 -531 31972 -223804 328 -532 32081 -224567 329 -533 32190 -225330 330 -534 32299 -226093 331 -535 32408 -226856 332 -536 32517 -227619 333 -537 32626 -2...

result:

ok ok Sum L = 5000

Test #17:

score: 0
Accepted
time: 0ms
memory: 3484kb

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
100 -493 -604 -73482 514374 -492 -603 -73337 513359 -491 -602 -73192 512344 -490 -601 -73047 511329 -489 -600 -72902 510314 -488 -599 -72757 509299 -487 -598 -72612 508284 -486 -597 -72467 507269 -485 -596 -72322 506254 -484 -595 -72177 505239 -483 -594 -72032 504224 -482 -593 -71887 503209 -481 ...

result:

ok ok Sum L = 5000

Test #18:

score: 0
Accepted
time: 1ms
memory: 3580kb

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
100 -191 49 -23374 163618 -190 48 -23265 162855 -189 47 -23156 162092 -188 46 -23047 161329 -187 45 -22938 160566 -186 44 -22829 159803 -185 43 -22720 159040 -184 42 -22611 158277 -183 41 -22502 157514 -182 40 -22393 156751 -181 39 -22284 155988 -180 38 -22175 155225 -179 37 -22066 154462 -178 36...

result:

ok ok Sum L = 5000

Test #19:

score: 0
Accepted
time: 1ms
memory: 3408kb

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
24 -1000 -1000 -144999 1014993 -1000 -999 -144981 1014867 -999 -1000 -144872 1014104 -1000 999 -109017 763119 -1000 1000 -108999 762993 -999 1000 -108872 762104 999 -1000 108874 -762118 1000 -1000 109001 -763007 1000 -999 109019 -763133 999 1000 144874 -1014118 1000 999 144983 -1014881 1000 1000 ...

result:

ok ok Sum L = 1200

Test #20:

score: 0
Accepted
time: 0ms
memory: 3392kb

input:

4
1000 1000 50
1000 -1000 50
-1000 1000 50
-1000 -1000 50

output:

50
8 -1000 -1000 -144999 1014993 -1000 1000 -108999 762993 1000 -1000 109001 -763007 1000 1000 145001 -1015007
8 -1000 -1000 -145017 1015120 -1000 1000 -109017 763120 1000 -1000 108983 -762880 1000 1000 144983 -1014880
8 -1000 -1000 -145035 1015247 -1000 1000 -109035 763247 1000 -1000 108965 -762753...

result:

ok ok Sum L = 400

Extra Test:

score: 0
Extra Test Passed