QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376493#7680. Subwayarnold518WA 2ms4028kbC++172.0kb2024-04-04 10:47:062024-04-04 10:47:07

Judging History

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

  • [2024-04-04 10:47:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4028kb
  • [2024-04-04 10:47:06]
  • 提交

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-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[i].x, y2=A[i].y;
        if(x1==x2) continue;
        if(((y2-y1)*(-3*P-x1))%(x2-x1)==0)
        {
            int y=(y2-y1)*(-3*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-(-3*P))/(A[j].x-(-3*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=-1;
        vector<pii> V;
        for(int j=1; j<=N; j++)
        {
            if(A[j].k>=i)
            {
                if(bef==-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)});
                }
                else
                {
                    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");
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 2 1
2 1 2
3 3 2

output:

2
13 999990000 333106 2 1 999990000 333109 999990001 333109 999990001 666437 999990000 666437 1 2 999990000 666440 999990001 666440 999990001 998992 999990000 998992 3 3 999990000 998995 
8 999990000 333107 2 1 999990000 333108 999990002 333108 999990002 998993 999990000 998993 3 3 999990000 998994 

result:

ok ok Sum L = 21

Test #2:

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

input:

1
1 1 1

output:

1
3 999990000 333218 1 1 999990000 333219 

result:

ok ok Sum L = 3

Test #3:

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

input:

1
1 1 50

output:

50
3 999990000 333169 1 1 999990000 333268 
3 999990000 333170 1 1 999990000 333267 
3 999990000 333171 1 1 999990000 333266 
3 999990000 333172 1 1 999990000 333265 
3 999990000 333173 1 1 999990000 333264 
3 999990000 333174 1 1 999990000 333263 
3 999990000 333175 1 1 999990000 333262 
3 99999000...

result:

ok ok Sum L = 150

Test #4:

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

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
248 999990000 -366427745 -885 -775 999990000 -366427646 999990001 -366427646 999990001 -332959857 999990000 -332959857 -306 -897 999990000 -332959758 999990001 -332959758 999990001 -327227806 999990000 -327227806 -870 -697 999990000 -327227707 999990001 -327227707 999990001 -315812233 999990000 -...

result:

ok ok Sum L = 5865

Test #5:

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

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
248 999990000 -405077379 -756 -909 999990000 -405077378 999990001 -405077378 999990001 -337911659 999990000 -337911659 -162 -959 999990000 -337911658 999990001 -337911658 999990001 -316949349 999990000 -316949349 -192 -890 999990000 -316949348 999990001 -316949348 999990001 -294769448 999990000 -2...

result:

ok ok Sum L = 248

Test #6:

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

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
248 999990000 -394605085 -552 -966 999990000 -394605076 999990001 -394605076 999990001 -338973510 999990000 -338973510 -637 -801 999990000 -338973501 999990001 -338973501 999990001 -293800093 999990000 -293800093 356 -986 999990000 -293800084 999990001 -293800084 999990001 -291216604 999990000 -29...

result:

ok ok Sum L = 695

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
248 999990000 -436181461 -767 -974 999990000 -436181442 999990001 -436181442 999990001 -421121890 999990000 -421121890 -813 -921 999990000 -421121871 999990001 -421121871 999990001 -370671028 999990000 -370671028 -313 -996 999990000 -370671009 999990001 -370671009 999990001 -360955126 999990000 -...

result:

ok ok Sum L = 1385

Test #8:

score: -100
Wrong Answer
time: 2ms
memory: 4028kb

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
248 999990000 -337378115 -282 -917 999990000 -337378016 999990001 -337378016 999990001 -311542584 999990000 -311542584 75 -958 999990000 -311542485 999990001 -311542485 999990001 -293979473 999990000 -293979473 24 -889 999990000 -293979374 999990001 -293979374 999990001 -280317945 999990000 -2803...

result:

wrong answer Sum of L too large.