QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#525505#6812. Draw a triangleucup-team3474AC ✓35ms4120kbC++203.0kb2024-08-20 17:17:572024-08-20 17:17:57

Judging History

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

  • [2024-08-20 17:17:57]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:4120kb
  • [2024-08-20 17:17:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
#define x1 aufhhakjs
#define x2 aiufqkjefbqkjf
#define y1 aifajskfnakjfkk
#define y2 aufhajksfkajbfwqf
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

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


void testify(__int128 xx){
    if(xx<-1e18||xx>1e18) assert(0);
}


bool check(__int128 xx){
    if(xx<-1e18||xx>1e18) return false;
    return true;
}

void __(){
    ll x1,y1,x2,y2;
    scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
    // cout<<x1<<" "<<y1<<endl;
    ll fz=y2-y1,fm=x2-x1;
    // cout<<fz<<" "<<fm<<endl;
    fm=-fm;
    if(y1==y2){
        printf("%lld %lld\n",x1,y1-1);
        return;
    }
    if(x1==x2){
        printf("%lld %lld\n",x1+1,y1);
        return;
    }
    if(fz<0){
        fz=-fz;
        fm=-fm;
    }
    ll MX=1e18,MN=-1e18;
    ll gg=__gcd(fz,fm);
    ll c=fz*x1+fm*y1;
    ll ax1,ax2,ay1,ay2;
    ll x,y;
    exgcd(fz/gg,abs(fm/gg),x,y);
    __int128 xx,yy,cm;
    fz/=gg,fm/=gg;
    cm=fz*fm;
    ll cc=c/gg+1;
    xx=x,y=yy;
    xx*=cc;
    xx%=cm;
    yy=(cc-fz*xx)/fm;
    

    if(xx>0){

        if(xx>MX){
            __int128 jian=(xx-MX+fm-1)/fm;
            __int128 xxx=xx-jian*fm;
            __int128 yyy=(cc-fz*xxx)/fm;
            if(check(xxx)&&check(yyy)){
                printf("%lld %lld\n",(ll)xxx,(ll)yyy);
                return;
            }
        }else{
            __int128 jia=(MX-xx)/fm;
            __int128 xxx=xx+jia*fm;
            __int128 yyy=(cc-fz*xxx)/fm;
            if(check(xxx)&&check(yyy)){
                printf("%lld %lld\n",(ll)xxx,(ll)yyy);
                return;
            }
        }

        __int128 xxx=xx%fm;
        __int128 yyy=(cc-fz*xxx)/fm;
        if(check(xxx)&&check(yyy)){
            printf("%lld %lld\n",(ll)xxx,(ll)yyy);
            return;
        }


    }else{
        if(xx<MN){
            __int128 jia=(MN-xx+fm-1)/fm;
            __int128 xxx=xx+jia*fm;
            __int128 yyy=(cc-fz*xxx)/fm;
            if(check(xxx)&&check(yyy)){
                printf("%lld %lld\n",(ll)xxx,(ll)yyy);
                return;
            }
        }else{
            __int128 jian=(xx-MN)/fm;
            __int128 xxx=xx-jian*fm;
            __int128 yyy=(cc-fz*xxx)/fm;
            if(check(xxx)&&check(yyy)){
                printf("%lld %lld\n",(ll)xxx,(ll)yyy);
                return;
            }
        }

        __int128 xxx=xx%fm;
        __int128 yyy=(cc-fz*xxx)/fm;
        if(check(xxx)&&check(yyy)){
            printf("%lld %lld\n",(ll)xxx,(ll)yyy);
            return;
        }

    }


    printf("%lld %lld\n",(ll)xx,(ll)yy);

    assert(0);
    // testify(xx);
    // testify(yy);
    // cout<<fz<<" "<<fm<<endl;
    // cout<<x*fz+y*fm<<" "<<fz+fm<<endl;
}


int main(){
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}

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

詳細信息

Test #1:

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

input:

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

output:

2 0
1 1
-1000000000000000000 -999999999999999999

result:

ok T=3 (3 test cases)

Test #2:

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

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
999999999999999887 996000000054894476
999999999999999896 992000000085003183
-999999999999999912 -987999999890745410
-999999999999999945 -983999999859335535
999999999999999963 980000000170791188
-999999999999999888 -976000000097507351
999999999999999956 971999999984137733
999999999999999...

result:

ok T=50000 (50000 test cases)

Test #3:

score: 0
Accepted
time: 25ms
memory: 4116kb

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:

0 -127910854
4 9583201
-6 -142955878
141 67839242
11 -32064558
28 229327125
-31 131360541
0 195868596
10 -103875504
142 -102613977
-4 27153103
-23 78743559
-46 97586750
22 -68875696
1 -83688863
0 97155929
11 -11920614
-78 70516433
-41 162941034
-26 159950793
9 -15271075
-11 120415757
-20 49339175
97...

result:

ok T=50000 (50000 test cases)

Test #4:

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

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
-45 -141564609
-19 -423005043
-4 -55820085
20 -271593674
1 53177061
-22 242322633
-23 259846193
-2 133222281
37 -253716444
0 -291464470
-20 198546381
13 -1265685
9 -333819889
-23 220491820
6 -120369612
-22 161709815
-10 -36819989
22 -300044525
-47 498673774
3 -464026960
-38 104343693
22 ...

result:

ok T=50000 (50000 test cases)

Test #5:

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

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:

-11 300193298
7 -41523057
19 -211390629
6 256605
-3 46181317
6 47629386
37 193554374
9 220061697
-15 -317904997
-4 439917227
-6 -139627498
17 235389176
-29 -314274677
-13 -29380675
-1 -114077538
-12 -193377259
-49 251410967
-8 -174006390
0 -143550294
-4 -348050804
-23 -298962751
-17 -185346989
-23 -...

result:

ok T=50000 (50000 test cases)

Test #6:

score: 0
Accepted
time: 25ms
memory: 3896kb

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:

-25 109096979
-23 209135611
7 -199152118
-21 -133192316
-21 166061120
72 48612702
39 118725404
68 180611456
-34 -22452738
-3 -198342029
44 118964220
42 64719440
-31 -132751897
-32 -114519719
22 -103782081
15 140817306
144 5477241
-4 -60091760
15 156067633
11 57373716
20 169785398
-8 -134837787
7 -16...

result:

ok T=49999 (49999 test cases)

Test #7:

score: 0
Accepted
time: 34ms
memory: 3812kb

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:

266772858 690432484
-999999999735258545 -252607027860955926
-999999999841925448 7740673117702878
1160818030 713546650
-999999999609929684 -167664773842175614
999999999931812312 322525588579316631
-493232151 -580589514
-117300853 44352240
-999999999311751345 338392346877020390
-3542253 -31276354781
9...

result:

ok T=50000 (50000 test cases)

Test #8:

score: 0
Accepted
time: 30ms
memory: 3880kb

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
492315397 -1923711761
112742509 -282791513
999999999941869273 102986803738631652
459627521 -768834120
-57740918 -1833494347
58837972 -6943398
-187044052 -1077426600
-999999999012655077 650392314099416503
-999999999388697707 -849559804977555107
-9999999999971112...

result:

ok T=50000 (50000 test cases)

Test #9:

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

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:

999999999980921746 488413458756637693
999999999428004214 553964586576344582
-999999999570594971 -315025249393246397
999999999945161807 581346867062012418
999999999910560031 660019266541889838
999999999800390605 630248394790702866
-999999999973576263 117754346106927322
-1132725863 1677750508
-2525216...

result:

ok T=50000 (50000 test cases)

Test #10:

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

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:

100685842 -556528909
255934168 302190473
11309755 -6156605164
-999999999968557242 13424931744783487
-366228545 1282667724
-39479264 -774871170
-999999999513972007 -573959889679767829
-999999999868599502 -618947767216995598
-999999999865758490 -357634806408650284
453213420 -846409459
158607620 -10616...

result:

ok T=50000 (50000 test cases)

Test #11:

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

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:

19026253 -64725540
999999999464792817 494158637293254489
-999999999457123181 3808495720275819
100812045 -2360054320
999999999982127149 -331032284373155896
999999999931436347 469166346556147293
67075737 128353343
999999999971469850 -1185624899524507
-999999999845097853 -653372408444771636
99999999999...

result:

ok T=50000 (50000 test cases)

Test #12:

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

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:

297420621 -906015335
-2511158 -13158231229
-999999999889471887 635477861486865140
1350252 -51075855482
999999999960277791 -658247568971994097
10822061 608636889
999999999816524476 361005428005184055
455737034 890635746
-551785821 -1965928454
130049017 -155248488
999999999828803844 381363341643855686...

result:

ok T=50000 (50000 test cases)

Test #13:

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

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:

999999999994870500 838539797381849467
-999999998727847284 110452237744504319
-10576381 1619903183
999999999983913720 -133828106929336589
-999999999798118392 -705196195362797734
-101375428 -4132180504
-999999999702297403 582844185987464758
71161752 1172376235
999999999688589693 -917249887073409830
-2...

result:

ok T=50000 (50000 test cases)

Test #14:

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

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:

999999999906336100 -363519222574506722
236411761 656308283
999999998968408435 76145828132019266
-9270099 -53602833
999999999944501498 822807904923950854
162912105 1033519616
439368857 235614788
-160046426 913074526
48638543 -452639985
999999999731779494 -268931918971653616
-999999999944002910 109620...

result:

ok T=50000 (50000 test cases)

Test #15:

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

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:

999999999957853347 -445550930776002134
30927 -791198083946
-107699857 -3087484985
999999999861649195 376930736914804048
-999999999731822542 158767833158332752
-9424534 4629789254
105366390 2051593222
-5672426 -4513215490
-52090302 2073201267
5335899 1733869674
-999999998788744822 -559600048855096765...

result:

ok T=50000 (50000 test cases)

Test #16:

score: 0
Accepted
time: 30ms
memory: 3872kb

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
-244940516 560073807
-541936137 1144053883
-999999999993971668 -18506714198320844
999999999934834825 319760460218183314
-999999999750040881 -360...

result:

ok T=50000 (50000 test cases)

Test #17:

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

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:

-742587546 -510815431
667540219 -818874929
31443672 408109710
-183568201 1098412300
999999999993562445 -185325822350917549
999999999964300798 -867394526516208690
-999999999522617125 616003959210933099
61674 -1474540311
-61872340 -869357738
-999999999815189357 442719727158370424
-438801981 -754840334...

result:

ok T=50000 (50000 test cases)

Test #18:

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

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
139940566 -2152677636
2509144 -3542891164
-999999999222238424 755078281740917518
91985485 183999823
999999999014901769 721474828389761631
-999999999598369466 -901419471267510853
-999999999777547434 45545181579765472
-68209101 225202772
-999999999510769460 -526...

result:

ok T=50000 (50000 test cases)

Test #19:

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

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:

999999999940699797 234248354867516928
62166715 1979389627
3693945 373571025
-999999999635675656 244362943806420417
999999999550378450 657025675676517908
-26908804 -328035228
891326125 -1422479531
-999999999599981638 846809506888677447
999999999971723568 362254862417520916
36656152 -1810305559
647972...

result:

ok T=50000 (50000 test cases)

Test #20:

score: 0
Accepted
time: 27ms
memory: 4116kb

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
6415268 619599813
44406 25729163762
-168625 42181319871
999999999744903333 192094631170615489
-999999998981925608 -432046702093986899
-11047713 -68000232
-10074354 479105738
-999999999487938551 577564039255678024
162061915 ...

result:

ok T=50000 (50000 test cases)

Test #21:

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

input:

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

output:

-1000000000000000000 -999999999999999999
-1000000000 -1000000001
-999999999 -1000000000

result:

ok T=3 (3 test cases)