QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269312#6812. Draw a triangleucup-team1001#AC ✓54ms3832kbC++232.1kb2023-11-29 15:04:312023-11-29 15:04:31

Judging History

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

  • [2023-11-29 15:04:31]
  • 评测
  • 测评结果:AC
  • 用时:54ms
  • 内存:3832kb
  • [2023-11-29 15:04:31]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define x1 jdfhnskjsdnbflj
#define y1 bhfgrbsw
#define int long long

int exgcd(int a, int b, __int128 &x, __int128 &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    __int128 temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}

void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int a = y2 - y1;
    int b = x1 - x2;
    int c = x2 * y1 - y2 * x1;
    __int128 x, y;
    int d = exgcd(a, b, x, y);
//    cout << x << " " << y << endl;
//    cout << c << " " << d << endl;
    x *= (-c + d) / d;
    y *= (-c + d) / d;
//    cout << x << " " << y << endl;
    auto ceil = [](__int128 a, __int128 b) -> __int128 {
        return (a + b - 1) / b;
    };
    const __int128 ma = 1000'000'000'000'000'000ll;
    if (x > ma) {
        if (b > 0) {
            __int128 n = ceil(x - ma, b);
            x -= n * b;
            y += n * a;
        } else {
            __int128 n = ceil(x - ma, -b);
            x += n * b;
            y -= n * a;
        }
    }
    if (x < -ma) {
        if (b > 0) {
            __int128 n = ceil(-ma - x, b);
            x += n * b;
            y -= n * a;
        } else {
            __int128 n = ceil(-ma - x, -b);
            x -= n * b;
            y += n * a;
        }
    }
    if (y > ma) {
        if (a > 0) {
            __int128 n = ceil(y - ma, a);
            x += n * b;
            y -= n * a;
        } else {
            __int128 n = ceil(y - ma, -a);
            x -= n * b;
            y += n * a;
        }
    }
    if (y < -ma) {
        if (a > 0) {
            __int128 n = ceil(-ma - y, a);
            x -= n * b;
            y += n * a;
        } else {
            __int128 n = ceil(-ma - y, -a);
            x += n * b;
            y -= n * a;
        }
    }
    cout << (int)x << " " <<(int) y << endl;
}

signed main() {
    IOS
    int t = 1;
    cin >> t;
    while (t--)solve();
}

//1
//999999999 0
//0 499999999

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 0 1 4
0 1 0 9
0 0 2 2

output:

2 0
1 0
0 1

result:

ok T=3 (3 test cases)

Test #2:

score: 0
Accepted
time: 36ms
memory: 3560kb

input:

50000
66620473 -33485015 66620223 -33485265
43307886 98029243 43307636 98028994
-88895230 -3180782 -88895480 -3181030
-90319745 20018595 -90319995 20018348
-56783257 84789686 -56783507 84789440
-81798038 90629147 -81798288 90628902
98942945 -939146 98942695 -939390
-42532151 -57203475 -42532401 -572...

output:

0 -100105487
13723647137 13723647137
10625410771 10625410771
-2267030938412 -2239717312648
-1090149184320 -1072566132960
8539561213 8539561213
-511914166638 -499725734099
424314498206 412417830032
319508495863 309201770190
-578593658835 -557743436895
735414464 735414464
-475560039227 -454656301239
3...

result:

ok T=50000 (50000 test cases)

Test #3:

score: 0
Accepted
time: 24ms
memory: 3584kb

input:

50000
57869123 -31462316 57868973 -31462566
-22048649 -27017563 -22048799 -27017812
80245618 -10283113 80245468 -10283361
-96265076 -90677482 -96265226 -90677729
22392625 4659329 22392475 4659083
-85852423 89101455 -85852573 89101210
-59733414 34194238 -59733564 34193994
-64971121 90615380 -64971271...

output:

-383732562 -767465124
1437479154 2395798590
-278763942756 -461032674558
172989475041 284923841244
8817758411 14429059218
75677936158 123836622804
-78816354856 -128076576641
-205662025800 -332976613200
241510584310 389533200500
938919977092 1508428815656
-271531094 -407296641
-696880821473 -111028469...

result:

ok T=50000 (50000 test cases)

Test #4:

score: 0
Accepted
time: 40ms
memory: 3524kb

input:

50000
-4816480 -62927672 -4816530 -62927922
38837454 51846136 38837404 51845887
81700780 -17769080 81700730 -17769328
-2355821 -67457821 -2355871 -67458068
38958908 -79915945 38958858 -79916191
-22432180 -56740626 -22432230 -56740871
-30176805 95059932 -30176855 95059688
-42037280 55545124 -42037330...

output:

0 -38845271
-7078219245 -35391096225
-10575123719 -52875618595
-47447055454 -234444274008
81478131720 400600814290
531770561 2658852805
-48464548072 -236264671851
-90946206673 -441738718126
-19983343602 -96586160743
139544142287 672349049201
-1457322350 -7286611750
-89345914470 -426874924690
1265746...

result:

ok T=50000 (50000 test cases)

Test #5:

score: 0
Accepted
time: 40ms
memory: 3532kb

input:

50000
47565990 63314613 47566040 63314364
-6671692 -8431430 -6671642 -8431678
-56437314 67409796 -56437264 67409549
-19754631 97449419 -19754581 97449173
22709358 -65094552 22709408 -65094797
-9253477 92786383 -9253427 92786139
60264780 -99332277 60264830 -99332520
42759753 13104536 42759803 1310429...

output:

-15009662161 75048310805
1038075557 -5190377785
179681954869 -887840247588
76990356 -378535917
-461813023 2309065115
9525883056 -46438679898
67744093837 -329042741494
33009261084 -159544761906
-174847788115 842448433645
-2199586039 10997930195
-62832387006 300199182362
23538925692 -111809897037
-361...

result:

ok T=50000 (50000 test cases)

Test #6:

score: 0
Accepted
time: 20ms
memory: 3616kb

input:

49999
86077178 -33791178 86077328 -33791427
70274103 92949056 70274253 92948808
-98644776 -36717042 -98644626 -36717289
-58640982 -37021140 -58640832 -37021386
47389280 88658595 47389430 88658350
41133739 -18298063 41133889 -18298307
16742668 91602345 16742818 91602102
64705012 76220813 64705162 762...

output:

-16364540625 27274234375
-407814367298 674462222839
507837871507 -836438847188
-36627896371 59936557698
-54800158281 89672986278
29167691472 -47397498642
124661740539 -201833294206
419921890268 -677293371400
-205443052534 330056051612
-1983420338 2975130507
1052833967444 -1677396490504
140764926942 ...

result:

ok T=49999 (49999 test cases)

Test #7:

score: 0
Accepted
time: 46ms
memory: 3560kb

input:

50000
-370035325 -480207325 197507381 563102266
-447653163 -13791299 712913474 279375990
-164085901 515918101 -746049282 520422889
-351774171 -526736185 986786085 570845376
-139080671 -314883129 -653624395 -401153986
371330972 295281720 716532063 406617905
713639850 932579042 -697994312 -837319029
-...

output:

543983023286575242 999999999382572508
-999999999735258545 -252607027860955926
-999999999841925448 7740673117702878
999999999927240046 819971723858782146
-999999999609929684 -167664773842175614
999999999931812312 322525588579316631
-797579353698884645 -999999998248619891
-450485054709837355 -99999999...

result:

ok T=50000 (50000 test cases)

Test #8:

score: 0
Accepted
time: 35ms
memory: 3828kb

input:

50000
38026624 -878076357 -552920439 -350794846
-412973070 -567080550 -956686128 247707367
293749788 -47698118 949332510 803776854
-37716684 -75717498 -384102742 -111390691
252319124 -407086186 -298274705 553686185
195690205 -960978213 693203670 751867944
-44794927 146815392 497184663 -657312706
244...

output:

999999999512555230 -892265220111306812
667306234792890259 -999999999435044924
769937747377379950 999999999402832053
999999999941869273 102986803738631652
573074169710045548 -999999999587526693
-290460098759920663 -999999999469476448
673996582308644782 -999999999532825380
-716056783903600516 -9999999...

result:

ok T=50000 (50000 test cases)

Test #9:

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

input:

50000
25273482 -271356160 203127555 -184489837
-289853919 200578127 408716355 587561320
440221844 -73945468 -375731352 -330991327
452223216 -181778460 -163936693 -539981093
538901710 569206009 766705704 719561034
-491626613 -671982599 527872032 -29445214
-63710429 421304993 -622588079 487115265
-476...

output:

999999999862352364 488413458698726811
999999999428004214 553964586576344582
-999999999570594971 -315025249393246397
999999999945161807 581346867062012418
999999999910560031 660019266541889838
999999999392591147 630248394533687912
-999999999694137438 117754346074022186
-843929568262775150 99999999894...

result:

ok T=50000 (50000 test cases)

Test #10:

score: 0
Accepted
time: 44ms
memory: 3748kb

input:

50000
-35259334 -701474112 311852823 -331381965
572375773 934385697 63613329 -82033074
963625204 106699315 855551972 -604089908
-239314379 -375979612 122091992 -380831468
-884798360 -827592392 -450362161 940295667
-209340085 -40153027 -361999245 620160834
877357984 882062152 315363830 559500049
-414...

output:

937907383232048360 999999999761055869
500544124678657968 999999999863903423
152046808192596331 999999999828287825
-999999999968557242 13424931744783487
-245737391395780671 -999999999294998042
-231191815212939544 999999999937735543
-999999999513972007 -573959889679767829
-999999999338143338 -61894776...

result:

ok T=50000 (50000 test cases)

Test #11:

score: 0
Accepted
time: 23ms
memory: 3532kb

input:

50000
-3663853 -177781773 173552690 705221364
-960654525 -342974336 754897176 504780355
494495391 471831124 -843629424 476927366
348629524 -909106658 627892786 725953059
-523367521 102557145 502351897 -236989097
-299381834 260178935 -743399500 51860789
335298045 -183924414 720046790 -631868047
17038...

output:

200697523547190454 999999999165032019
999999999464792817 494158637293254489
-999999999457123181 3808495720275819
170796980516062041 999999999295062066
999999999982127149 -331032284373155896
999999999709427514 469166346451988220
858922231955533292 -999999999914750444
999999999665688650 -1185624899161...

result:

ok T=50000 (50000 test cases)

Test #12:

score: 0
Accepted
time: 43ms
memory: 3528kb

input:

50000
87994422 -469168315 -282663695 303996144
-153451281 -314512069 -168298547 948863838
-293926308 -170703744 789655924 -859296264
930120677 671761062 934908485 938519828
-62509863 497504980 258338790 286307134
166058928 434063507 329625200 250123198
170938223 -712363899 -476975593 -946264304
-351...

output:

479403977356557283 -999999999733441009
-11752057409716182 999999999365536819
-999999999212232992 635477861056494815
17948082140803980 999999999800728624
999999999960277791 -658247568971994097
889235605623094957 -999999999820079923
999999999816524476 361005428005184055
705341985526712069 999999999613...

result:

ok T=50000 (50000 test cases)

Test #13:

score: 0
Accepted
time: 40ms
memory: 3624kb

input:

50000
75983688 322870644 646834996 801552184
519110129 -976686263 -819619684 -828820558
570394281 246976850 519558688 367109464
621047758 927882674 148954683 991061997
88827271 210457738 -857995083 -457237784
112341241 -890456500 223281366 792319429
-102888330 389111504 665082474 -58495814
-70874021...

output:

999999999566732019 838539797022838312
-999999998727847284 110452237744504319
-423162297262445121 999999999950049703
999999999983913720 -133828106929336589
-999999999798118392 -705196195362797734
-65926854992597928 -999999999495671724
-999999999702297403 582844185987464758
986009195748680989 99999999...

result:

ok T=50000 (50000 test cases)

Test #14:

score: 0
Accepted
time: 49ms
memory: 3624kb

input:

50000
-805634427 81825426 509577423 -396279363
-267738158 -532191054 179134956 521282089
893958536 -637235181 -336434702 -730924494
209380302 -981860939 -104731724 351669816
693569118 -145872073 215960733 -538852028
278991643 856418697 472101398 561793859
773440456 -666647571 296326173 621945233
-88...

output:

999999999029528200 -363519222255770196
424190323848958477 999999999417246725
999999998968408435 76145828132019266
-235549142394575215 999999998942546497
999999999562414790 822807904609566890
655442889780494700 -999999999856296406
370259931314659360 -999999998790691376
-601250908782151217 -9999999991...

result:

ok T=50000 (50000 test cases)

Test #15:

score: 0
Accepted
time: 43ms
memory: 3832kb

input:

50000
725941728 -610067425 488068370 -504082729
476613211 -620476119 476920048 -111480150
245593358 -660602217 471175896 888995542
280795134 -289504448 -967836825 -760152213
-486471673 -224674228 934607251 -450295850
-694176146 751372343 -891227475 -364721717
830792306 -773436907 523127672 424703167...

output:

999999999838916668 -445550930723009786
602828433672441 999999999847698072
-145574898956145123 -999999998752940548
999999999861649195 376930736914804048
-999999999731822542 158767833158332752
-176554411356033249 -999999999281610846
256785196741975860 -999999999574501448
-205149814553852225 -999999999...

result:

ok T=50000 (50000 test cases)

Test #16:

score: 0
Accepted
time: 32ms
memory: 3528kb

input:

50000
104556371 -685734071 -731906759 -604652123
396789892 -935692027 -576229790 -207110549
-578953998 541207525 -516985486 542399334
-878495739 -596088045 119106374 -251106029
-363926466 866046756 158763085 -478051966
599120280 -275757280 -282204734 820871313
-588932159 -793669810 680396515 -770178...

output:

999999999667635050 -96934276754272284
-999999999850297210 748783905143633392
-999999999971006221 -19232492878602884
-999999999045892183 -345811232220639276
-388877351158707435 999999999369959425
-803667730740336777 999999999109589563
-999999999993971668 -18506714198320844
999999999833538239 31976046...

result:

ok T=50000 (50000 test cases)

Test #17:

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

input:

50000
-913971105 -802525545 -62443082 646851152
582546207 -691701688 -263954188 574883995
-88743623 992720648 272194515 -762942323
-840733072 -332078482 -575663610 244914353
440623464 752008161 -470122956 920792991
-757686511 643488102 708042881 -627877550
185019277 307661180 -692173668 848015507
75...

output:

-587513256346173957 -999999999160822060
668332514816083814 -999999999524061892
205585094461305148 -999999998705439632
-459398187067296713 -999999999821732660
999999999932846017 -185325822339665227
999999999231436102 -867394525880525864
-999999999522617125 616003959210933099
39348025687609234 9999999...

result:

ok T=50000 (50000 test cases)

Test #18:

score: 0
Accepted
time: 54ms
memory: 3620kb

input:

50000
185492989 3104323 -418943377 -567314244
-716676172 339998445 -419312863 -525301490
-610060612 777476899 -418834808 -571211717
39944725 -455257290 -829398804 201165129
-466129455 -464184034 735772464 931681523
-466599024 -740319024 563884212 3148693
-505528308 -808674422 -6340257 -358696593
-85...

output:

-999999999487759530 -943719800624538869
343653450443143708 -999999999495616166
141786473897742612 -999999999596156836
-999999999222238424 755078281740917518
861044182671116434 999999998950478470
999999999014901769 721474828389761631
-999999999598369466 -901419471267510853
-999999999777547434 4554518...

result:

ok T=50000 (50000 test cases)

Test #19:

score: 0
Accepted
time: 38ms
memory: 3608kb

input:

50000
-474636599 -626920443 712875021 -348747799
-342048305 37518714 -249508888 482083100
-410519206 -225607946 27339059 407774804
-345676873 559668812 88853181 453485769
999517103 522173138 135806165 -45307125
-285232985 -711392209 656546715 686223071
-736883128 630709030 260930401 -627544060
34322...

output:

999999999346943987 234248354728430606
208157512721773950 999999999891690257
691301214918648255 999999999417039525
-999999999635675656 244362943806420417
999999999550378450 657025675676517908
-673847597563659844 -999999998956858524
793014963234944439 -999999999202717471
-999999999599981638 8468095068...

result:

ok T=50000 (50000 test cases)

Test #20:

score: 0
Accepted
time: 23ms
memory: 3628kb

input:

50000
626800159 776374206 -41956635 417375236
-536924579 414783144 847473468 181350188
103033152 456387414 906877647 -901512211
784792043 -200142589 761424984 571942095
-319313812 593906734 -329157602 -688825321
790537948 -567376329 -989657217 -909342264
82546755 272767210 -982948739 -187576605
3536...

output:

999999999987979330 536815436509598294
-999999999008294551 168616935514495383
591976373143001180 -999999999493643587
30264892022949361 -999999999682621818
-7674081557131299 -999999999042673162
999999998676786234 192094630965435928
-999999998981925608 -432046702093986899
-343351647605681988 -999999999...

result:

ok T=50000 (50000 test cases)

Test #21:

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

input:

3
-1000000000 -1000000000 1000000000 1000000000
-1000000000 -1000000000 1000000000 -1000000000
-1000000000 -1000000000 -1000000000 1000000000

output:

0 1
0 -999999999
-999999999 0

result:

ok T=3 (3 test cases)