QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377243#7680. Subwayarnold518AC ✓1ms4080kbC++172.9kb2024-04-05 06:51:282024-04-05 06:51:28

Judging History

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

  • [2024-04-05 06:51:28]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4080kb
  • [2024-04-05 06:51:28]
  • 提交

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 = 1e9-4e3;

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

int N, K;
vector<Data> A1, A2;
int B1, B2;

int main()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
    {
        Data p;
        scanf("%d%d%d", &p.x, &p.y, &p.k);
        if(p.x>0) A1.push_back(p);
        else A2.push_back(p);
        K=max(K, p.k);
    }

    vector<int> V1, V2;
    for(int i=0; i<A1.size(); i++) for(int j=i+1; j<A1.size(); j++)
    {
        int x1=A1[i].x, y1=A1[i].y, x2=A1[j].x, y2=A1[j].y;
        if(x1==x2) continue;
        if(((y2-y1)*(-P-x1))%(x2-x1)==0)
        {
            int y=(y2-y1)*(-P-x1)/(x2-x1)+y1;
            if(-P<=y && y<=P) V1.push_back(y);
        }
    }
    sort(V1.begin(), V1.end());
    for(int i=0; i<=P; i++)
    {
        if(!binary_search(V1.begin(), V1.end(), i)) { B1=i; break; }
        if(!binary_search(V1.begin(), V1.end(), -i)) { B1=-i; break; }
    }
    for(int i=0; i<A1.size(); i++) A1[i].p=(ll)(A1[i].y-B1)*(Q-(-P))/(A1[i].x-(-P))+B1;

    for(int i=0; i<A2.size(); i++) for(int j=i+1; j<A2.size(); j++)
    {
        int x1=A2[i].x, y1=A2[i].y, x2=A2[j].x, y2=A2[j].y;
        if(x1==x2) continue;
        if(((y2-y1)*(P-x1))%(x2-x1)==0)
        {
            int y=(y2-y1)*(P-x1)/(x2-x1)+y1;
            if(-P<=y && y<=P) V2.push_back(y);
        }
    }
    sort(V2.begin(), V2.end());
    for(int i=0; i<=P; i++)
    {
        if(!binary_search(V2.begin(), V2.end(), i)) { B2=i; break; }
        if(!binary_search(V2.begin(), V2.end(), -i)) { B2=-i; break; }
    }
    for(int i=0; i<A2.size(); i++) A2[i].p=(ll)(A2[i].y-B2)*(-Q-P)/(A2[i].x-P)+B2;

    sort(A1.begin(), A1.end(), [&](const Data &p, const Data &q) { return p.p<q.p; });
    sort(A2.begin(), A2.end(), [&](const Data &p, const Data &q) { return p.p>q.p; });

    for(int i=0; i+1<A1.size(); i++) assert(A1[i].p<A1[i+1].p);
    for(int i=0; i+1<A2.size(); i++) assert(A2[i].p>A2[i+1].p);

    printf("%d\n", K);
    for(int i=1; i<=K; i++)
    {
        vector<pii> V;

        for(int j=0; j<A1.size(); j++)
        {
            if(A1[j].k>=i)
            {
                V.push_back({Q+i, A1[j].p-(K-i+1)});
                V.push_back({A1[j].x, A1[j].y});
                V.push_back({Q+i, A1[j].p+(K-i)});
            }
        }
        V.push_back({Q+i, 1e9-K+i});
        V.push_back({-Q-i, 1e9-K+i});
        for(int j=0; j<A2.size(); j++)
        {
            if(A2[j].k>=i)
            {
                V.push_back({-Q-i, A2[j].p+(K-i)});
                V.push_back({A2[j].x, A2[j].y});
                V.push_back({-Q-i, A2[j].p-(K-i+1)});
            }
        }
        
        printf("%d ", V.size());
        for(auto [x, y] : V) printf("%d %d ", x, y);
        printf("\n");
    }
}

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

详细

Test #1:

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

input:

3
1 2 1
2 1 2
3 3 2

output:

2
11 999996001 997998 2 1 999996001 998001 999996001 1997994 1 2 999996001 1997997 999996001 2991015 3 3 999996001 2991018 999996001 999999999 -999996001 999999999 
8 999996002 997999 2 1 999996002 998000 999996002 2991016 3 3 999996002 2991017 999996002 1000000000 -999996002 1000000000 

result:

ok ok Sum L = 19

Test #2:

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

input:

1
1 1 1

output:

1
5 999996001 998997 1 1 999996001 998998 999996001 1000000000 -999996001 1000000000 

result:

ok ok Sum L = 5

Test #3:

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

input:

1
1 1 50

output:

50
5 999996001 998948 1 1 999996001 999047 999996001 999999951 -999996001 999999951 
5 999996002 998949 1 1 999996002 999046 999996002 999999952 -999996002 999999952 
5 999996003 998950 1 1 999996003 999045 999996003 999999953 -999996003 999999953 
5 999996004 998951 1 1 999996004 999044 999996004 9...

result:

ok ok Sum L = 250

Test #4:

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

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
152 999996001 -669413334 334 -893 999996001 -669413235 999996001 -584024920 202 -702 999996001 -584024821 999996001 -468637093 961 -919 999996001 -468636994 999996001 -341154261 662 -567 999996001 -341154162 999996001 -317395411 736 -551 999996001 -317395312 999996001 -238871736 348 -322 99999600...

result:

ok ok Sum L = 3679

Test #5:

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

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
152 999996001 -843686790 30 -869 999996001 -843686789 999996001 -477868034 333 -637 999996001 -477868033 999996001 -463233905 360 -630 999996001 -463233904 999996001 -433807253 473 -639 999996001 -433807252 999996001 -413377834 749 -723 999996001 -413377833 999996001 -210761700 115 -235 999996001 ...

result:

ok ok Sum L = 152

Test #6:

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

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
152 999996001 -744343887 17 -757 999996001 -744343878 999996001 -727136466 356 -986 999996001 -727136457 999996001 -723291603 348 -975 999996001 -723291594 999996001 -563039106 618 -911 999996001 -563039097 999996001 -531366039 594 -847 999996001 -531366030 999996001 -483747199 846 -893 999996001 ...

result:

ok ok Sum L = 433

Test #7:

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

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
152 999996001 -656944865 166 -766 999996001 -656944846 999996001 -555553898 269 -705 999996001 -555553879 999996001 -535416987 87 -582 999996001 -535416968 999996001 -487058590 932 -941 999996001 -487058571 999996001 -485669744 326 -644 999996001 -485669725 999996001 -472640101 60 -501 999996001 ...

result:

ok ok Sum L = 863

Test #8:

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

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
152 999996001 -891160167 75 -958 999996001 -891160068 999996001 -868161508 24 -889 999996001 -868161409 999996001 -730603143 173 -857 999996001 -730603044 999996001 -652001236 273 -830 999996001 -652001137 999996001 -414442528 537 -637 999996001 -414442429 999996001 -395082271 139 -450 999996001 ...

result:

ok ok Sum L = 6904

Test #9:

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

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
152 999996001 -771092139 197 -923 999996001 -771092040 999996001 -761639438 267 -965 999996001 -761639339 999996001 -666194240 417 -944 999996001 -666194141 999996001 -589464858 481 -873 999996001 -589464759 999996001 -537389742 150 -618 999996001 -537389643 999996001 -474131311 643 -779 99999600...

result:

ok ok Sum L = 7600

Test #10:

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

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
152 999996001 -4995040 1 -5 999996001 -4994941 999996001 -4990054 2 -5 999996001 -4989955 999996001 -3996042 1 -4 999996001 -3995943 999996001 -3980137 5 -4 999996001 -3980038 999996001 -2994052 2 -3 999996001 -2993953 999996001 -1998046 1 -2 999996001 -1997947 999996001 -1994061 3 -2 999996001 -...

result:

ok ok Sum L = 4372

Test #11:

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

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
152 999996001 -8973051 3 -5 999996001 -8973048 999996001 -8955195 5 -5 999996001 -8955192 999996001 -7991982 1 -4 999996001 -7991979 999996001 -7984005 2 -4 999996001 -7984002 999996001 -6986004 2 -3 999996001 -6986001 999996001 -6979039 3 -3 999996001 -6979036 999996001 -5993986 1 -2 999996001 -5...

result:

ok ok Sum L = 262

Test #12:

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

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
152 999996001 -5994037 1 -5 999996001 -5993938 999996001 -5988054 2 -5 999996001 -5987955 999996001 -4995039 1 -4 999996001 -4994940 999996001 -4980113 4 -4 999996001 -4980014 999996001 -3996041 1 -3 999996001 -3995942 999996001 -3988072 3 -3 999996001 -3987973 999996001 -3984100 4 -3 999996001 -...

result:

ok ok Sum L = 7531

Test #13:

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

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
152 999996001 441959072 163 514 999996001 441959169 999996001 442339415 162 514 999996001 442339512 999996001 442720414 161 514 999996001 442720511 999996001 443102069 160 514 999996001 443102166 999996001 443484384 159 514 999996001 443484481 999996001 443867358 158 514 999996001 443867455 99999...

result:

ok ok Sum L = 3554

Test #14:

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

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
152 999996001 782533287 191 932 999996001 782533384 999996001 783372915 191 933 999996001 783373012 999996001 784212543 191 934 999996001 784212640 999996001 785052171 191 935 999996001 785052268 999996001 785891799 191 936 999996001 785891896 999996001 786731427 191 937 999996001 786731524 99999...

result:

ok ok Sum L = 3554

Test #15:

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

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
152 999996001 999999951 -999996001 999999951 -999996001 470203480 -74 505 -999996001 470203381 -999996001 468835851 -75 504 -999996001 468835752 -999996001 467470765 -76 503 -999996001 467470666 -999996001 466108214 -77 502 -999996001 466108115 -999996001 464748190 -78 501 -999996001 464748091 -9...

result:

ok ok Sum L = 3718

Test #16:

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

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
152 999996001 -418976895 370 -574 999996001 -418976796 999996001 -418552483 369 -573 999996001 -418552384 999996001 -418127450 368 -572 999996001 -418127351 999996001 -417701796 367 -571 999996001 -417701697 999996001 -417275518 366 -570 999996001 -417275419 999996001 -416848616 365 -569 99999600...

result:

ok ok Sum L = 3736

Test #17:

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

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
152 999996001 999999951 -999996001 999999951 -999996001 -384347828 -444 -555 -999996001 -384347927 -999996001 -384773883 -445 -556 -999996001 -384773982 -999996001 -385199348 -446 -557 -999996001 -385199447 -999996001 -385624226 -447 -558 -999996001 -385624325 -999996001 -386048516 -448 -559 -999...

result:

ok ok Sum L = 3583

Test #18:

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

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
152 999996001 999999951 -999996001 999999951 -999996001 41141823 -191 49 -999996001 41141724 -999996001 40336062 -190 48 -999996001 40335963 -999996001 39528946 -189 47 -999996001 39528847 -999996001 38720471 -188 46 -999996001 38720372 -999996001 37910634 -187 45 -999996001 37910535 -999996001 3...

result:

ok ok Sum L = 4033

Test #19:

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

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
38 999996001 -500248674 999 -1000 999996001 -500248575 999996001 -499998550 1000 -1000 999996001 -499998451 999996001 -499498551 1000 -999 999996001 -499498452 999996001 499498451 1000 999 999996001 499498550 999996001 499998450 1000 1000 999996001 499998549 999996001 500248574 999 1000 999996001...

result:

ok ok Sum L = 1900

Test #20:

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

input:

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

output:

50
14 999996001 -499998550 1000 -1000 999996001 -499998451 999996001 499998450 1000 1000 999996001 499998549 999996001 999999951 -999996001 999999951 -999996001 499998549 -1000 1000 -999996001 499998450 -999996001 -499998451 -1000 -1000 -999996001 -499998550 
14 999996002 -499998549 1000 -1000 99999...

result:

ok ok Sum L = 700

Extra Test:

score: 0
Extra Test Passed