QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377235#7680. Subwayarnold518WA 1ms4080kbC++172.8kb2024-04-05 05:55:462024-04-05 05:55:47

Judging History

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

  • [2024-04-05 05:55:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4080kb
  • [2024-04-05 05:55:46]
  • 提交

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[i].x, y2=A1[i].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[i].x, y2=A2[i].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(), V1.end(), i)) { B2=i; break; }
        if(!binary_search(V2.begin(), V1.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; });

    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");
    }
}

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
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: 3732kb

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: 3788kb

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: 3852kb

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: 1ms
memory: 4064kb

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: 3792kb

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: 1ms
memory: 3736kb

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: 3708kb

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: 0ms
memory: 4080kb

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: -100
Wrong Answer
time: 1ms
memory: 3788kb

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:

wrong answer Duplicated points on polyline 1.