QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#525495#6812. Draw a triangleucup-team3474TL 24ms4068kbC++202.1kb2024-08-20 17:08:432024-08-20 17:08:44

Judging History

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

  • [2024-08-20 17:08:44]
  • 评测
  • 测评结果:TL
  • 用时:24ms
  • 内存:4068kb
  • [2024-08-20 17:08:43]
  • 提交

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;

    while(!check(xx)||!check(yy)){
        if(xx<MN){
            __int128 ad=(MN-xx+fm-1)/fm;
            xx+=ad*fm;
            // yy-=ad*fz;
            yy=(cc-fz*xx)/fm;
        }
        if(xx>MX){
            __int128 mn=(xx-MX+fm-1)/fm;
            xx-=mn*fm;
            yy=(cc-fz*xx)/fm;
        }

        if(yy<MN){
            __int128 ad=(MN-yy+fz-1)/fz;
            yy+=ad*fz;
            xx=(cc-fm*yy)/fz;
        }
        if(yy>MX){
            __int128 mn=(yy-MX+fz-1)/fz;
            yy-=mn*fz;
            xx=(cc-fm*yy)/fz;
        }
    }


    printf("%lld %lld\n",(ll)xx,(ll)yy);
    testify(xx);
    testify(yy);
    // cout<<fz<<" "<<fm<<endl;
    // cout<<x*fz+y*fm<<" "<<fz+fm<<endl;
}


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

详细

Test #1:

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

input:

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

output:

2 0
1 1
0 1

result:

ok T=3 (3 test cases)

Test #2:

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

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
12137 54906677
5771 85009011
-39162 109215811
-15195 140649459
463 170791678
-1138 -97508571
48206 -15815368
9863 -82444258
-15335 20835439
464 29417024
-49977 -20951516
3367 141403625
-43128 -152696475
-14492 -133093215
67 94489275
-8487 -73753695
53437 18944221
-13804 -78404284
-47700...

result:

ok T=50000 (50000 test cases)

Test #3:

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

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:

-12 -127910874
2154 9586770
-4656 -142963566
23991 67878515
136 -32064353
328 229327615
-2506 131356515
-450 195867867
5110 -103867276
3592 -102608434
-14 27153087
-20723 78710577
-6646 97576278
672 -68874669
5851 -83679659
1380 97158091
861 -11919288
-10278 70500589
-8366 162928158
-376 159950254
2...

result:

ok T=50000 (50000 test cases)

Test #4:

score: 0
Accepted
time: 22ms
memory: 3840kb

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
-8295 -141605694
-719 -423008515
-10354 -55871214
1245 -271587647
21 53177159
-2322 242311409
-6073 259816790
-2 133222281
8987 -253673305
-110 -291464998
-6720 198514355
338 -1264138
1459 -333813016
-1948 220482734
246 -120368484
-447 161707826
-5960 -36847716
2147 -300034665
-2247 4986...

result:

ok T=50000 (50000 test cases)

Test #5:

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

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:

-4411 300215210
257 -41524297
1769 -211399274
1581 248856
-273 46182640
1056 47624262
7087 193520111
1284 220055526
-10665 -317853664
-79 439917587
-4006 -139608378
2767 235376086
-7079 -314241260
-113 -29380203
-131 -114076927
-2037 -193367782
-1599 251418190
-1358 -174000126
-8400 -143511486
-104 ...

result:

ok T=50000 (50000 test cases)

Test #6:

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

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:

-3325 109102457
-2198 209139207
5257 -199160763
-46 -133192275
-351 166061659
7722 48600258
2739 118721030
5468 180602744
-35884 -22395139
-18 -198342005
22394 118928609
5442 64710872
-831 -132750633
-5657 -114510869
772 -103783256
765 140816136
10794 5460698
-1204 -60089904
3065 156062936
86 573736...

result:

ok T=49999 (49999 test cases)

Test #7:

score: -100
Time Limit Exceeded

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:


result: