QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288160#7750. Revenge on My BossUNos_maricones#WA 695ms9340kbC++142.1kb2023-12-22 07:59:012023-12-22 07:59:02

Judging History

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

  • [2023-12-22 07:59:02]
  • 评测
  • 测评结果:WA
  • 用时:695ms
  • 内存:9340kb
  • [2023-12-22 07:59:01]
  • 提交

answer

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

#define ff first
#define ss second
#define pb push_back
#define mp make_pair

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

const int N = 100'005;

struct frac {
    ll a, b;
    frac () {}
    frac (ll a, ll b): a ( a ), b ( b ) {}
    bool operator < ( frac s ) const {
        return a * s.b < s.a * b;
    }
    frac operator + ( ll x ) {
        return frac ( a + x*b, b );
    }
};

int t, n;
ll a[N], b[N], c[N];
int ind[N], ind_res[N];
pair <ll, frac> X_Y[N];
ll s_b, res;

void reset () {
    s_b = 0; res = LLONG_MAX;
}

void genArrXY (ll mi) {
    for ( int i = 0; i < n; ++i ) {
        X_Y[i] = mp(a[i]-b[i], frac(mi - a[i]*c[i] - s_b*c[i], c[i]));
    }
}

bool cmp ( int indA, int indB ) {
    auto A = X_Y[indA], B = X_Y[indB];
    if ( A.ff < 0 and B.ff < 0 )
        return B.ss < A.ss;
    if ( A.ff < 0 or B.ff < 0 )
        return A.ff < B.ff;
    return A.ss+A.ff < B.ss+B.ff;
}

ll getMax () {
    ll maxi = 0, pref = 0;
    for ( int k = 0; k < n; ++k ) {
        int i = ind[k];
        maxi = max ( maxi, (a[i]+s_b+pref)*c[i] );
        pref += a[i] - b[i];
    }
    return maxi;
}

bool check ( ll mi ) {
    genArrXY ( mi );
    iota ( ind, ind+n, 0 );
    sort ( ind, ind+n, cmp );
    ll currAns = getMax ();
    if ( currAns < res ) {
        res = currAns;
        copy ( ind, ind+n, ind_res );
    }
    return currAns <= mi;
}

void getAns () {
    ll lo = 0, hi = LLONG_MAX/3, mi;
    while ( lo < hi ) {
        mi = (lo+hi)/2;
        if ( check ( mi ) ) {
            hi = res;
        } else {
            lo = mi+1;
        }
    }
}

int main () {
        
    #ifndef LOCAL
    #endif

    scanf ( "%d", &t );
    while ( t-- ) {
        reset ();
        scanf ( "%d", &n );
        for ( int i = 0; i < n; ++i ) {
            scanf ( "%lld%lld%lld", a+i, b+i, c+i );
            s_b += b[i];
        }
        getAns ();
        for ( int i = 0; i < n; ++i )
            printf ( "%d%c", ind_res[i]+1, " \n"[i==n-1] );
    }

    return 0;
}

詳細信息

Test #1:

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

input:

2
4
1 1 4
5 1 5
1 9 1
9 8 1
9
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 8
3 2 7

output:

3 2 1 4
3 8 4 2 5 9 7 1 6

result:

ok correct

Test #2:

score: 0
Accepted
time: 553ms
memory: 9108kb

input:

1
100000
581297 102863 1
742857 42686 1
676710 233271 1
443055 491162 1
442056 28240 1
769277 331752 1
8608 369730 1
495112 525554 1
787449 938154 1
441186 850694 1
84267 925450 1
740811 32385 1
834021 37680 1
257878 564126 1
90618 914340 1
239641 463103 1
40687 343062 1
587737 458554 1
103684 48666...

output:

70717 6151 48237 28851 35679 19561 94252 73342 13089 34865 69194 82763 50242 22597 3745 24913 97923 53671 77581 47428 82224 93567 61401 50007 4886 54152 28731 91278 99937 6691 26840 6048 46204 66044 60735 44469 20513 45842 18701 46818 27203 9261 50507 8020 72391 54368 86201 18839 64763 61758 40939 3...

result:

ok correct

Test #3:

score: 0
Accepted
time: 532ms
memory: 9184kb

input:

1
99999
30245 831673 1
495617 185056 1
53028 422589 1
503558 778900 1
636981 480008 1
966864 78785 1
644954 303138 1
153080 225499 1
876411 832264 1
758904 549009 1
945000 441995 1
83780 789901 1
883282 832556 1
300776 548075 1
806599 108342 1
354979 831549 1
152110 819163 1
613891 812479 1
856259 6...

output:

42779 26176 16432 93736 36110 21022 69840 33300 88899 48735 24934 97468 58044 16598 54398 41611 25297 90410 54385 14754 38513 7374 40518 45724 3741 95478 36354 5270 92123 87433 5901 57489 42968 40570 60847 61715 65894 68944 27887 3727 38578 14748 15072 79314 41234 42830 79639 35429 60443 63782 12370...

result:

ok correct

Test #4:

score: 0
Accepted
time: 538ms
memory: 9180kb

input:

1
100000
361850 684411 2
188930 167748 2
676274 449963 1
970095 784305 1
412379 854673 1
208323 612179 1
296548 633970 1
560983 633064 2
848966 248363 2
741057 340814 1
393854 435721 2
302707 834494 1
229770 235051 2
875992 747523 2
314215 448795 1
531181 809914 2
786505 95721 1
86557 773136 1
44527...

output:

16321 7131 35939 39108 40409 52183 74664 70501 56736 85313 78033 67062 11374 28893 29910 76382 77675 16590 14329 99654 33902 81051 93812 47118 54934 27805 77685 57504 62353 47016 36321 65709 30222 17782 92966 93722 32969 69339 20699 31143 29231 20833 32593 17020 77014 2193 20753 96742 16406 11108 56...

result:

ok correct

Test #5:

score: 0
Accepted
time: 546ms
memory: 9032kb

input:

1
99999
810798 413222 2
974394 310117 1
987184 606577 2
30598 6635 1
607304 306441 1
438614 583404 1
932894 375890 1
994760 333009 2
937928 950984 2
58774 6426 1
287291 728073 1
421484 592009 1
470520 62631 1
918891 764176 2
997492 642796 1
679223 178361 2
865224 571822 2
112711 192469 1
165146 9387...

output:

38004 71563 34947 26525 22330 44909 47503 52297 78657 28797 29991 22680 7929 68438 15865 70932 27655 90081 30923 61265 20749 31006 35033 64820 20963 86257 21420 27746 3451 43480 36392 44360 16524 76128 8052 60705 72335 52826 82386 88960 8813 60213 12369 84977 96785 82723 23228 1372 34613 67012 54683...

result:

ok correct

Test #6:

score: 0
Accepted
time: 521ms
memory: 9104kb

input:

1
100000
142404 976360 1
924602 517001 3
610429 601247 2
529839 44745 3
606894 456914 2
488586 84093 1
360297 674019 1
435366 740573 3
943187 591275 3
8223 87831 2
703441 689095 1
673115 893499 3
817008 689318 2
237211 187815 1
472404 15953 2
822721 932534 2
275427 591484 3
393890 928933 1
11058 141...

output:

51206 37611 59015 50700 80703 52328 53240 43032 8346 8263 41296 64851 47024 78344 80432 99788 79216 80112 84718 81292 91031 58261 72331 98859 85353 71212 34320 28981 4231 54595 26732 77344 6558 79986 1230 64802 4053 35487 35001 47208 53390 6142 58146 9701 11407 53054 48744 52885 2922 93682 94826 636...

result:

ok correct

Test #7:

score: 0
Accepted
time: 527ms
memory: 9088kb

input:

1
99999
815544 929362 2
644659 659371 3
954043 790565 3
398854 42883 3
577627 875978 2
718877 831126 1
996643 640131 2
869143 249030 3
32149 261192 1
325941 753442 3
372686 238344 2
48789 426822 2
57757 260002 1
280109 237173 3
931489 242658 2
970763 300980 2
578337 100288 1
611532 282858 3
506737 2...

output:

27161 35747 25296 34165 9717 57726 57073 11785 24054 83782 88554 68057 42695 23849 49568 78850 8501 69293 52754 11183 39393 98733 35177 37567 85341 22705 9930 96866 82802 47796 9996 57550 29112 27373 52932 83741 39761 26412 12546 99295 22521 45367 72274 77249 22609 44764 11050 29507 28236 24580 4570...

result:

ok correct

Test #8:

score: 0
Accepted
time: 529ms
memory: 9096kb

input:

1
100000
179854 525204 1
403379 866255 3
544585 817939 4
832686 337889 3
577217 283347 1
960336 331815 3
424045 970964 1
309749 591186 4
37408 677291 2
308093 545247 1
45732 199365 1
267715 728311 2
404245 919393 4
855325 436620 1
406400 774600 3
146965 279345 3
955837 376846 3
860006 276218 2
28724...

output:

24436 23350 14823 6635 16186 28793 85545 28010 65377 49593 9096 36992 62631 55712 98568 36492 47289 43010 3738 84762 70128 48544 57069 75781 59468 17061 39547 97907 7290 48134 29862 84143 19385 42718 49107 41621 94075 30404 65165 61273 78021 98586 89053 17836 39470 53504 98341 37199 90866 20337 9343...

result:

ok correct

Test #9:

score: 0
Accepted
time: 570ms
memory: 9340kb

input:

1
99999
628802 478207 4
156140 784432 3
920902 198745 3
925893 336026 4
772142 702412 2
190627 335745 3
93095 937076 4
710822 356539 2
126370 604104 4
625811 243562 3
714977 524422 2
386493 485827 2
677699 522781 4
898224 453274 1
89677 777113 3
262303 647792 3
291451 852947 2
886160 662847 1
848327...

output:

25476 82833 20708 62196 65199 34417 31863 24519 6410 2660 86721 49138 41559 14233 14538 12861 77995 81983 14766 34516 89431 97096 88505 83091 38565 74389 94338 68659 85344 5885 21302 17145 57922 53773 76261 38160 50466 83035 84330 45236 77809 51690 49927 6715 43442 92483 55111 97458 84347 80388 4440...

result:

ok correct

Test #10:

score: 0
Accepted
time: 550ms
memory: 9104kb

input:

1
100000
993111 41344 2
849452 991316 3
287252 969223 4
392430 565624 3
547540 852885 3
240598 836434 5
520498 11013 2
151428 698695 1
98926 987499 3
607963 259559 2
131127 518148 5
638124 530420 3
991483 116764 5
440736 876913 1
564589 309054 1
438505 593453 5
701654 872609 4
391530 399311 5
628832...

output:

40304 73884 46665 34832 83244 13265 71577 34416 81702 34262 55470 14854 96718 20687 75463 16459 34149 34475 8088 30861 77981 72514 92859 39810 55233 80930 35735 85535 89142 73204 61946 48999 88803 32652 61389 33091 39964 64315 41786 22045 69345 85883 21081 60246 54103 75958 66900 11113 17122 41787 3...

result:

ok correct

Test #11:

score: 0
Accepted
time: 536ms
memory: 9164kb

input:

1
99999
633547 770155 1
634916 133686 5
855058 382733 4
485637 596466 2
742466 271949 3
470889 583467 1
156844 977125 2
585205 464048 5
187887 690121 3
892977 925171 2
57268 34693 4
981093 255232 2
232232 977047 5
516338 893566 4
247866 311567 3
586547 994603 5
4565 348710 5
417684 977428 3
124510 7...

output:

48240 97152 38149 92052 85126 48738 420 86878 1608 77274 25520 16300 85538 61415 87215 9020 23040 6708 82083 15814 66859 99499 16595 23692 38022 28113 27468 68026 15427 8746 33174 14077 72913 80575 26563 66510 41324 17717 35068 39018 73663 45534 19933 82609 30013 16591 13958 58164 4681 66871 61356 1...

result:

ok correct

Test #12:

score: 0
Accepted
time: 571ms
memory: 9320kb

input:

1
100000
997857 590189 5
552421 307866 1
221408 153211 4
952174 826064 4
742055 646614 4
712348 116860 2
808438 307957 5
250004 806205 1
193147 297708 2
875130 941168 5
473418 995714 5
975828 556721 3
578721 379543 1
834658 317206 4
722778 876212 3
730045 972968 6
414768 657972 1
633455 746596 6
970...

output:

58367 96255 27046 51517 62990 14996 43792 8080 70637 88785 56968 29155 30934 51774 59548 29427 90925 70372 58953 41857 33191 96145 17321 23404 87318 1596 46324 13075 9593 11090 26264 56726 77126 83979 64736 94161 65026 25548 5002 62346 36677 33190 44945 17805 87787 14720 15278 41786 55909 91963 1146...

result:

ok correct

Test #13:

score: 0
Accepted
time: 560ms
memory: 9092kb

input:

1
99999
414101 318999 4
305181 450235 4
789213 599425 5
12677 889610 6
936981 98382 2
942639 831190 3
444784 241365 4
683780 538854 3
314812 329 6
192848 447995 3
142664 320771 6
384205 90044 2
595278 174418 6
877557 109667 2
181863 102918 3
910791 341415 2
526191 134073 2
659609 133225 3
690293 561...

output:

35478 18624 78085 84422 64480 8449 51230 4571 89366 63494 34463 41028 36180 21314 30197 81273 40400 69808 42147 3988 98521 2452 13595 43642 69108 39646 93137 95922 39452 1217 10651 80682 35534 34784 49882 14755 73947 23645 38923 95063 30177 52114 49164 98219 208 98408 5373 71603 93716 11385 60484 18...

result:

ok correct

Test #14:

score: 0
Accepted
time: 583ms
memory: 9040kb

input:

1
100000
778411 171737 3
31198 657119 3
155563 369903 1
511917 119207 6
679674 248855 4
992610 588775 5
872187 572198 6
91683 913714 4
254664 416428 3
175000 463992 3
815710 281793 4
603132 358830 2
165958 576913 2
420069 533307 7
656775 410667 2
278481 287076 5
160586 153734 2
164979 126586 2
27930...

output:

10495 78296 86975 66984 43573 26013 68012 28684 21728 84715 73054 55225 80985 71471 19208 75959 3227 49197 78757 51517 90370 45175 30815 33044 22612 38359 10155 50081 38746 20159 29238 80523 64318 24082 8081 80300 49009 47185 51927 50099 81484 31393 93483 48777 27137 18152 11576 10916 63727 96750 55...

result:

ok correct

Test #15:

score: 0
Accepted
time: 581ms
memory: 9184kb

input:

1
99999
451551 900548 5
783958 575297 1
756073 750709 5
605124 150049 5
907304 667919 2
190198 335808 4
508533 538310 7
525460 422171 6
409034 310537 1
268526 129603 1
484955 798337 5
946101 116345 4
215220 404493 1
495671 549960 7
340051 637372 6
169627 688226 2
206600 629835 3
191133 480511 4
3188...

output:

54269 84814 11203 22266 69715 2067 98594 58686 77120 97588 24647 22779 41418 74818 11208 77299 68401 83198 48458 83840 10016 73446 1390 25559 11910 57243 94269 68865 21808 3045 36095 77465 14015 56072 4637 32888 22833 39225 85587 87637 73770 70840 9918 92119 76820 76804 18268 93252 20843 97020 35269...

result:

ok correct

Test #16:

score: 0
Accepted
time: 561ms
memory: 9096kb

input:

1
100000
783156 687878 1
477270 782181 2
122423 521187 1
814765 379647 8
906893 42584 3
464361 836497 8
935935 677655 6
966066 829735 7
348885 726636 6
474870 178304 5
901105 792063 5
940836 193643 7
785900 806988 3
38183 973599 4
814963 945121 3
570021 666591 6
840996 939097 7
406903 216975 2
62090...

output:

72039 60446 79913 606 67084 74974 38540 46212 13925 18473 33329 54770 80078 8805 94531 69295 94929 82414 11017 59740 69274 52094 98394 64031 74594 3026 65376 40859 93220 16215 56539 99398 84080 23209 38748 2719 88190 13990 91697 28371 94299 21350 58000 46528 27 406 68868 13024 13756 32181 12213 6526...

result:

ok correct

Test #17:

score: 0
Accepted
time: 498ms
memory: 9332kb

input:

1
99999
45362 965532 6
708808 306508 2
624384 151389 1
467716 670928 1
39438 96594 5
942210 88149 7
892926 875304 8
241522 637190 1
564772 772170 8
835563 334036 7
104129 627390 5
911109 785971 7
389695 864643 9
475004 239058 3
432237 738985 3
818115 349146 8
665532 910961 8
964582 950889 9
682361 7...

output:

17464 54738 19792 69939 35189 77452 89261 55631 50252 91841 70330 4005 64528 98810 51735 25631 44169 2070 89979 41652 86742 62362 45691 29466 82233 78136 91194 51184 6693 82962 21064 93923 22440 83984 47051 39021 91148 97090 43528 17339 33500 58672 69501 561 7869 9766 74630 46576 40530 51413 7570 62...

result:

ok correct

Test #18:

score: 0
Accepted
time: 520ms
memory: 9108kb

input:

1
100000
545343 214678 2
896330 34297 10
225650 145117 5
3539 141992 10
866014 337066 4
787360 33077 10
990193 565400 7
746446 687990 6
657093 370479 9
221001 777823 3
818490 795673 2
891597 771810 3
322069 291555 3
680477 429062 4
131032 471991 3
498884 709254 9
4962 615960 7
537100 173421 1
166345...

output:

47267 41095 99945 82746 72235 4514 7505 33683 57213 5896 21646 65793 2233 37477 35903 26024 55083 75580 81907 2157 93532 35053 37297 29849 58079 67046 3739 68803 90621 34886 53352 54246 56947 73238 88362 25725 54684 92792 65858 7259 30656 70002 31250 66964 37747 13385 86380 82236 46760 47662 82866 1...

result:

ok correct

Test #19:

score: 0
Accepted
time: 532ms
memory: 9088kb

input:

1
99999
336110 764075 4
762927 765956 4
275286 70789 5
459972 469529 7
870966 316414 7
498229 41636 11
830500 307315 6
854475 488251 5
759873 905341 5
993842 970385 9
217019 809676 12
207189 933113 4
625602 520131 7
736635 340574 11
921162 795091 6
552353 769663 10
406594 84507 8
465432 768495 3
892...

output:

39708 59543 43462 38768 62809 86685 85130 49266 10175 30405 5060 45395 16901 19161 77253 78326 74569 15283 81622 25091 32911 13276 24367 31315 53191 86779 19835 56034 94131 84931 2385 7006 43089 26503 35302 20787 17665 96835 31205 81685 18723 58976 78156 39068 12414 83152 77700 16443 27841 74989 144...

result:

ok correct

Test #20:

score: 0
Accepted
time: 564ms
memory: 9108kb

input:

1
100000
108561 606864 17
350323 824178 19
354491 276661 2
386504 972995 8
126712 330871 13
27512 558033 16
821693 489290 10
531173 946706 11
851074 696984 13
215023 489278 3
550601 849390 9
18144 714207 18
493423 166694 1
682070 122973 15
480819 38485 4
803701 169413 20
175493 785397 12
948045 5586...

output:

75830 42942 27955 67628 18688 75983 38085 55857 99543 58665 84286 98998 62210 79210 59646 20199 18423 96728 65122 77421 90405 52319 32112 50628 76760 47925 52882 92378 23843 58452 908 20803 85457 44246 89707 12492 61643 74369 62071 90435 5029 72372 58509 36921 3618 49681 66178 35530 49608 3543 52130...

result:

ok correct

Test #21:

score: 0
Accepted
time: 590ms
memory: 9336kb

input:

1
99999
270178 61120 9
118244 697562 5
796784 638127 10
716782 572441 25
868171 877138 2
451141 273737 29
917860 184163 26
669039 916520 30
900920 422991 7
772136 494308 18
675065 814143 30
968370 228164 17
447803 120035 26
195744 975315 19
310881 998911 19
512798 212819 4
789254 622264 22
984709 59...

output:

40137 5954 84879 13698 97786 83795 24220 24459 79395 99256 72457 96580 64413 25163 69801 34854 83596 7423 90706 88839 38803 16892 91637 19046 79416 30020 78757 9334 4192 86062 72933 27990 51333 17602 33609 75946 32500 4186 51747 2025 96710 94070 92015 66672 69739 24229 51979 45692 29176 34656 33789 ...

result:

ok correct

Test #22:

score: 0
Accepted
time: 574ms
memory: 9096kb

input:

1
100000
87815 816125 15
712301 586652 26
997911 895483 38
726884 50324 43
427717 312286 28
196351 258982 19
474976 452448 13
371565 914341 28
848695 643798 25
229795 39321 27
129910 753647 6
206296 219095 38
680062 142384 26
752256 980514 31
628293 803374 32
592071 806785 7
70061 583309 35
732498 3...

output:

91856 68167 54045 70962 56607 12074 19415 40950 56580 27223 78432 86849 52217 24146 93734 46920 62508 941 99732 23778 20805 44874 15261 84221 86023 27614 78728 28278 34192 54860 54949 76596 80771 70120 85957 75815 52991 22237 20514 80807 57607 81299 31493 61250 55697 68579 46442 13520 88697 44615 28...

result:

ok correct

Test #23:

score: 0
Accepted
time: 596ms
memory: 9052kb

input:

1
99999
969047 371 41
853468 252554 79
784554 756858 19
945912 189669 56
28679 367615 21
745635 438170 93
394681 487499 76
986024 222074 12
796761 902579 3
934082 772826 5
848868 475664 57
928859 487080 17
447261 415165 48
324804 77833 94
513254 520849 43
811124 531448 22
414298 235550 92
662853 204...

output:

41617 69476 22349 42877 49036 44100 55797 47684 17642 61367 21015 5928 60421 94902 63629 51537 41225 92090 1341 55407 50764 79386 92827 39635 76780 44973 55189 84540 3426 94028 19108 64882 30657 14953 75080 41940 44855 39038 39158 30651 22540 80746 57236 52623 38781 39532 83418 57354 45600 31028 303...

result:

ok correct

Test #24:

score: 0
Accepted
time: 600ms
memory: 9312kb

input:

1
100000
14578 331976 83
739173 945866 58
769064 123208 197
657914 688910 162
63712 334500 95
112850 488141 182
673605 139094 109
8038 662680 177
139883 875134 102
240255 754978 10
139120 891814 83
967220 706007 107
811284 728949 43
749285 653050 130
42454 995761 196
897079 899138 87
585743 869946 6...

output:

90508 94750 27222 98260 80046 51121 56997 85539 55322 91100 17379 96156 22969 13531 10457 30621 86229 18277 36510 92827 55960 30867 58396 33774 91809 70195 11030 79401 31090 94637 24041 81483 46426 40803 23017 89624 18025 61078 92413 91500 55935 81594 3394 31037 49079 38664 15546 25652 88003 60915 2...

result:

ok correct

Test #25:

score: 0
Accepted
time: 628ms
memory: 9072kb

input:

1
99999
776558 379481 222
389786 326445 297
33988 301992 167
922081 171748 27
44539 631883 366
435819 942194 271
728896 223581 455
306860 878391 458
944588 214055 460
459371 939603 266
655301 555228 355
491970 417096 153
318104 764115 348
829143 260691 86
14484 737924 368
508188 763016 368
738889 88...

output:

51087 24925 9188 80737 75625 49059 13150 17689 4942 14937 41090 15393 54230 7347 65007 36235 81067 31749 80027 45190 50983 32941 45815 3118 77029 47944 18060 87580 39178 10109 71391 12284 54426 78322 56688 36466 29023 50964 8976 4073 50273 63636 83987 96474 46305 27725 98185 36169 13266 69800 99536 ...

result:

ok correct

Test #26:

score: 0
Accepted
time: 650ms
memory: 9336kb

input:

1
100000
953776 515469 53
574495 620563 408
331343 705288 552
307179 689650 745
108389 820839 791
831194 34474 881
928795 832739 27
162288 848143 103
438197 683261 522
872355 234923 123
275412 349154 731
403641 327600 231
642668 821247 651
639908 457535 877
184578 621090 792
483486 866841 827
382761...

output:

4481 77517 55861 82021 91171 10278 91599 22352 62997 88175 21543 95213 3653 42138 64829 7098 69951 46439 75512 4374 40173 11528 80373 6310 21548 60450 68611 88084 12345 94012 90077 19911 83423 13985 384 69712 88308 69715 52689 60124 14250 17160 25248 66750 17052 98894 79338 69625 79851 25187 18434 6...

result:

ok correct

Test #27:

score: 0
Accepted
time: 680ms
memory: 9096kb

input:

1
99999
128495 399445 763
873699 750462 2051
771645 791001 3841
668391 425718 3815
274257 54791 3769
572299 402750 3749
622972 357997 1273
354814 50592 1657
409819 763434 3342
941450 774102 2301
705607 604543 3333
441889 400571 2267
563457 738075 3090
751849 8690 1656
524888 757409 1699
294794 33160...

output:

59747 83810 55200 87084 45820 27249 44444 80277 96910 44267 49337 46391 99077 43308 29471 90913 8622 86230 91783 97679 64912 29568 86567 17657 78874 60441 82493 24132 64950 69905 46445 71561 84500 76107 90240 62907 12272 3753 71573 31014 33888 16842 93642 26316 90084 8250 68748 61042 85844 99123 620...

result:

ok correct

Test #28:

score: 0
Accepted
time: 695ms
memory: 9340kb

input:

1
100000
722958 355226 2094
266625 467230 8712
979360 944520 2487
295170 735423 2727
722419 313725 3199
789942 961946 9194
700692 559861 7780
649116 795879 2218
690710 741191 3253
493019 510759 8703
230105 693648 3581
776356 568494 6123
384478 553056 8000
262437 617457 2646
944585 4132 9669
239024 3...

output:

84561 1956 1921 79444 50520 20450 55307 96079 67301 91853 61420 42651 21163 9444 12373 97592 96096 9322 30475 72842 19132 28577 77890 87950 81719 17283 87180 80783 12157 69705 36917 92110 732 31518 1661 23690 41130 51353 23548 12879 43835 82974 26007 73034 12545 28964 2061 39954 9803 17593 70166 771...

result:

ok correct

Test #29:

score: -100
Wrong Answer
time: 106ms
memory: 9108kb

input:

1
99999
846662 746684 27049
416087 114018 39556
827768 480922 19619
538880 640896 35309
974134 999365 37801
462745 682933 806
606482 571441 8720
401083 408557 32312
797890 970757 39099
378069 473292 33198
452952 185965 42390
524236 671077 29109
746622 849987 48916
692368 638905 26915
476085 504542 1...

output:

74386 53567 48714 19603 59779 44501 4552 16788 84444 97045 90186 24343 55181 40681 77851 78085 82972 43265 51343 81583 60073 24559 26850 95556 62752 12263 25590 27045 81584 43197 38645 91088 97971 60904 25728 33540 9919 62923 15250 12446 21626 48526 15682 61051 2153 93143 61689 93983 32609 71499 543...

result:

wrong answer Wrong Answer on Case#1