QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377245#7680. Subwayarnold518AC ✓1ms4068kbC++172.1kb2024-04-05 06:55:362024-04-05 06:55:36

Judging History

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

  • [2024-04-05 06:55:36]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4068kb
  • [2024-04-05 06:55:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 50;
const int P = 1e3;
const int Q = 4e8-1e4;

struct Data
{
    int x, y, k, p;
};

int N, K;
Data A[MAXN+10];
int B;

int main()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].k), K=max(K, A[i].k);

    vector<int> V;
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++)
    {
        int x1=A[i].x, y1=A[i].y, x2=A[j].x, y2=A[j].y;
        if(x1==x2) continue;
        if(((y2-y1)*(-2*P-x1))%(x2-x1)==0)
        {
            int y=(y2-y1)*(-2*P-x1)/(x2-x1)+y1;
            if(-P<=y && y<=P) V.push_back(y);
        }
    }
    sort(V.begin(), V.end());
    for(int i=0; i<P; i++)
    {
        if(!binary_search(V.begin(), V.end(), i)) { B=i; break; }
        if(!binary_search(V.begin(), V.end(), -i)) { B=-i; break; }
    }

    for(int j=1; j<=N; j++)
    {
        A[j].p=(ll)(A[j].y-B)*(Q-(-2*P))/(A[j].x-(-2*P))+B;
    }
    sort(A+1, A+N+1, [&](const Data &p, const Data &q) { return p.p<q.p; });

    printf("%d\n", K);
    for(int i=1; i<=K; i++)
    {
        int bef=-1e9-100;
        vector<pii> V;
        for(int j=1; j<=N; j++)
        {
            if(A[j].k>=i)
            {
                if(bef==-1e9-100)
                {
                    V.push_back({Q, A[j].p-(K-i+1)});
                    V.push_back({A[j].x, A[j].y});
                    V.push_back({Q, A[j].p+(K-i)});
                }
                else
                {
                    V.pop_back();
                    V.push_back({Q+i, bef});
                    V.push_back({Q+i, A[j].p-(K-i+1)});

                    //V.push_back({Q, A[j].p-(K-i+1)});
                    V.push_back({A[j].x, A[j].y});
                    V.push_back({Q, A[j].p+(K-i)});
                }
                bef=A[j].p+(K-i);
            }
        }
        printf("%d ", V.size());
        for(auto [x, y] : V) printf("%d %d ", x, y);
        printf("\n");
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

input:

3
1 2 1
2 1 2
3 3 2

output:

2
9 399990000 199794 2 1 399990001 199797 399990001 399790 1 2 399990001 399793 399990001 599087 3 3 399990000 599090 
6 399990000 199795 2 1 399990002 199796 399990002 599088 3 3 399990000 599089 

result:

ok ok Sum L = 15

Test #2:

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

input:

1
1 1 1

output:

1
3 399990000 199895 1 1 399990000 199896 

result:

ok ok Sum L = 3

Test #3:

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

input:

1
1 1 50

output:

50
3 399990000 199846 1 1 399990000 199945 
3 399990000 199847 1 1 399990000 199944 
3 399990000 199848 1 1 399990000 199943 
3 399990000 199849 1 1 399990000 199942 
3 399990000 199850 1 1 399990000 199941 
3 399990000 199851 1 1 399990000 199940 
3 399990000 199852 1 1 399990000 199939 
3 39999000...

result:

ok ok Sum L = 150

Test #4:

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

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
150 399990000 -278021395 -885 -775 399990001 -278021296 399990001 -246720779 -870 -697 399990001 -246720680 399990001 -239923308 -888 -667 399990001 -239923209 399990001 -217713413 -668 -725 399990001 -217713314 399990001 -211802189 -306 -897 399990001 -211802090 399990001 -199382188 -371 -812 39...

result:

ok ok Sum L = 3579

Test #5:

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

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
150 399990000 -292277113 -756 -909 399990001 -292277112 399990001 -208700941 -162 -959 399990001 -208700940 399990001 -200415866 -571 -716 399990001 -200415865 399990001 -196898717 -192 -890 399990001 -196898716 399990001 -176369185 -197 -795 399990001 -176369184 399990001 -171228103 30 -869 39999...

result:

ok ok Sum L = 150

Test #6:

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

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
150 399990000 -266845496 -552 -966 399990001 -266845487 399990001 -235065002 -637 -801 399990001 -235064993 399990001 -220499192 -888 -613 399990001 -220499183 399990001 -208088328 -962 -540 399990001 -208088319 399990001 -206949508 -792 -625 399990001 -206949499 399990001 -194941954 -615 -675 399...

result:

ok ok Sum L = 423

Test #7:

score: 0
Accepted
time: 0ms
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
150 399990000 -315970981 -767 -974 399990001 -315970962 399990001 -310356060 -813 -921 399990001 -310356041 399990001 -236154148 -313 -996 399990001 -236154129 399990001 -228566867 -285 -980 399990001 -228566848 399990001 -215380317 -258 -938 399990001 -215380298 399990001 -208951054 -325 -875 39...

result:

ok ok Sum L = 843

Test #8:

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

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
150 399990000 -213499854 -282 -917 399990001 -213499755 399990001 -201754607 -749 -631 399990001 -201754508 399990001 -196157355 -958 -511 399990001 -196157256 399990001 -184671055 75 -958 399990001 -184670956 399990001 -175688235 24 -889 399990001 -175688136 399990001 -157751151 173 -857 3999900...

result:

ok ok Sum L = 6804

Test #9:

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

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
150 399990000 -232975366 -302 -989 399990001 -232975267 399990001 -232940890 -367 -951 399990001 -232940791 399990001 -215380357 -882 -602 399990001 -215380258 399990001 -170540929 -126 -799 399990001 -170540830 399990001 -170265722 267 -965 399990001 -170265623 399990001 -168044026 197 -923 3999...

result:

ok ok Sum L = 7500

Test #10:

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

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
150 399990000 -2202202 -2 -5 399990001 -2202103 399990001 -2200000 0 -5 399990001 -2199901 399990001 -2198900 1 -5 399990001 -2198801 399990001 -2197802 2 -5 399990001 -2197703 399990001 -2005016 -5 -4 399990001 -2004917 399990001 -2004011 -4 -4 399990001 -2003912 399990001 -2001004 -1 -4 3999900...

result:

ok ok Sum L = 4272

Test #11:

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

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
150 399990000 -2205465 -5 -5 399990001 -2205462 399990001 -2196657 3 -5 399990001 -2196654 399990001 -2194465 5 -5 399990001 -2194462 399990001 -2003963 -4 -4 399990001 -2003960 399990001 -2002960 -3 -4 399990001 -2002957 399990001 -2001957 -2 -4 399990001 -2001954 399990001 -2000956 -1 -4 3999900...

result:

ok ok Sum L = 258

Test #12:

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

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
150 399990000 -2205513 -5 -5 399990001 -2205414 399990001 -2204408 -4 -5 399990001 -2204309 399990001 -2203304 -3 -5 399990001 -2203205 399990001 -2201100 -1 -5 399990001 -2201001 399990001 -2198900 1 -5 399990001 -2198801 399990001 -2197802 2 -5 399990001 -2197703 399990001 -2003008 -3 -4 399990...

result:

ok ok Sum L = 7431

Test #13:

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

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
150 399990000 95051216 163 514 399990001 95051313 399990001 95095181 162 514 399990001 95095278 399990001 95139186 161 514 399990001 95139283 399990001 95183232 160 514 399990001 95183329 399990001 95227319 159 514 399990001 95227416 399990001 95271446 158 514 399990001 95271543 399990001 9531561...

result:

ok ok Sum L = 3456

Test #14:

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

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
150 399990000 170147164 191 932 399990001 170147261 399990001 170329725 191 933 399990001 170329822 399990001 170512286 191 934 399990001 170512383 399990001 170694848 191 935 399990001 170694945 399990001 170877409 191 936 399990001 170877506 399990001 171059971 191 937 399990001 171060068 39999...

result:

ok ok Sum L = 3456

Test #15:

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

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
150 399990000 97174351 -123 456 399990001 97174450 399990001 97335596 -122 457 399990001 97335695 399990001 97496669 -121 458 399990001 97496768 399990001 97657571 -120 459 399990001 97657670 399990001 97818301 -119 460 399990001 97818400 399990001 97978861 -118 461 399990001 97978960 399990001 9...

result:

ok ok Sum L = 3618

Test #16:

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

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
150 399990000 -96875749 370 -574 399990001 -96875650 399990001 -96747798 369 -573 399990001 -96747699 399990001 -96619739 368 -572 399990001 -96619640 399990001 -96491571 367 -571 399990001 -96491472 399990001 -96363295 366 -570 399990001 -96363196 399990001 -96234911 365 -569 399990001 -96234812...

result:

ok ok Sum L = 3636

Test #17:

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

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
150 399990000 -160315357 -493 -604 399990001 -160315258 399990001 -159943800 -492 -603 399990001 -159943701 399990001 -159572736 -491 -602 399990001 -159572637 399990001 -159202163 -490 -601 399990001 -159202064 399990001 -158832081 -489 -600 399990001 -158831982 399990001 -158462489 -488 -599 39...

result:

ok ok Sum L = 3483

Test #18:

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

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
150 399990000 -50 -142 0 399990001 49 399990001 215346 -143 1 399990001 215445 399990001 430975 -144 2 399990001 431074 399990001 646837 -145 3 399990001 646936 399990001 862931 -146 4 399990001 863030 399990001 1079259 -147 5 399990001 1079358 399990001 1295820 -148 6 399990001 1295919 399990001...

result:

ok ok Sum L = 3933

Test #19:

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

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
36 399990000 -399992050 -1000 -1000 399990001 -399991951 399990001 -399592457 -999 -1000 399990001 -399592358 399990001 -399592058 -1000 -999 399990001 -399591959 399990001 -133375175 999 -1000 399990001 -133375076 399990001 -133330716 1000 -1000 399990001 -133330617 399990001 -133197386 1000 -99...

result:

ok ok Sum L = 1800

Test #20:

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

input:

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

output:

50
12 399990000 -399992050 -1000 -1000 399990001 -399991951 399990001 -133330716 1000 -1000 399990001 -133330617 399990001 133330616 1000 1000 399990001 133330715 399990001 399991950 -1000 1000 399990000 399992049 
12 399990000 -399992049 -1000 -1000 399990002 -399991952 399990002 -133330715 1000 -1...

result:

ok ok Sum L = 600

Extra Test:

score: 0
Extra Test Passed