QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590418#6812. Draw a triangleDixiky_215RE 32ms3812kbC++202.1kb2024-09-26 00:01:222024-09-26 00:01:22

Judging History

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

  • [2024-09-26 00:01:22]
  • 评测
  • 测评结果:RE
  • 用时:32ms
  • 内存:3812kb
  • [2024-09-26 00:01:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll =__int128;
// using ll = long long;
int t;
ll x,y,a,b,c;
void ex_gcd(ll al,ll bl)
{
	if(bl==0LL)
	{
		x=1LL;y=0LL;return;
	}
	else
	{
		ex_gcd(bl,al%bl);
		ll tmp=x;
		x=y;y=tmp-y*(al/bl);
	}
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

    long long x1,x2,y1,y2,x3,y3;
    cin>>t;
    while(t--)
    {
        cin>>x1>>y1>>x2>>y2;
    //    x1 = rnd() % 10 + 1; y1 = rnd() % 10 + 1; x2 = rnd() % 10 + 1; y2 = rnd() % 10 + 1;
        if(x1==x2)
        {
            cout<<x1+1LL<<" 1\n";
            continue;
        }
        if(y1==y2)
        {
            cout<<"1 "<<y1+1LL<<'\n';
            continue;
        }
        a=y1-y2;b=x2-x1;
        c=x2*y1-x1*y2;
        ll gcdk=__gcd(a,b);



        ll num_l=c/gcdk;
        if(c%gcdk==0LL) num_l--;
        ll num_r=c/gcdk;
        if(c%gcdk==0LL) num_r++;

        ll sum1=c-num_l*gcdk;
        ll sum2=num_r*gcdk-c;
        ll num;
        if(sum1<=sum2) num=num_l;
        else num=num_r;


    //    cerr<<a<<" "<<b<<" "<<c<<"  asd"<<endl;
        ex_gcd(a,b);
        // cerr<<x<<" "<<y<<" "<<c<<"  asd"<<endl;
		x*=num;y*=num;
		ll aa=b/gcdk,bb=a/gcdk;
		if(x<-1e18)
		{
			ll sum=-1e18-x;
			ll numk=sum/aa;
			if(sum%aa) numk++;
			x+=aa*numk;
			y-=bb*numk;
		}

		if(x>1e18)
		{
			ll sum=x-1e18;
			ll numk=sum/aa;
			if(sum%aa) numk++;
			x-=aa*numk;
			y+=bb*numk;
		}
        
		if(y<-1e18)
		{
			ll sum=-1e18-y;
			ll numk=sum/bb;
			if(sum%bb) numk++;
			x-=aa*numk;
			y+=bb*numk;
		}

		if(y>1e18)
		{
			ll sum=y-1e18;
			ll numk=sum/bb;
			if(sum%bb) numk++;
			x+=aa*numk;
			y-=bb*numk;
		}
        // cerr << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
        assert(x <= 1E18 and x >= -1E18);
        assert(y >= -1E18 and y <= 1E18);
        
        cout<<format("{}", x) <<" "<< format("{}", y) <<'\n';
		// cout<<x<<" "<<y<<"\n";
    }
    return 0;
}
/*
1
464263912 393228064 151248499 729744865
*/

詳細信息

Test #1:

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

input:

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

output:

2 1
1 1
0 -1

result:

ok T=3 (3 test cases)

Test #2:

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

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 -100105489
13723647135 13723647135
10625410769 10625410769
-2267030938578 -2239717312812
-1090149184444 -1072566133082
8539561211 8539561211
-511914166722 -499725734181
424314497992 412417829824
319508495801 309201770130
-578593659057 -557743437109
735414462 735414462
-475560039409 -454656301413
3...

result:

ok T=50000 (50000 test cases)

Test #3:

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

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:

-383732564 -767465128
1437479148 2395798580
-278763942808 -461032674644
172989475007 284923841188
8817758389 14429059182
75677936136 123836622768
-78816354872 -128076576667
-205662025842 -332976613268
241510584248 389533200400
938919976970 1508428815460
-271531098 -407296647
-696880821591 -111028469...

result:

ok T=50000 (50000 test cases)

Test #4:

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

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 -38845273
-7078219247 -35391096235
-10575123721 -52875618605
-47447055488 -234444274176
81478131696 400600814172
531770559 2658852795
-48464548088 -236264671929
-90946206687 -441738718194
-19983343614 -96586160801
139544142265 672349049095
-1457322352 -7286611760
-89345914488 -426874924776
1265746...

result:

ok T=50000 (50000 test cases)

Test #5:

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

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:

-15009662159 75048310795
1038075559 -5190377795
179681954903 -887840247756
76990332 -378535799
-461813021 2309065105
9525883040 -46438679820
67744093823 -329042741426
33009261072 -159544761848
-174847788137 842448433751
-2199586037 10997930185
-62832387024 300199182448
23538925684 -111809896999
-361...

result:

ok T=50000 (50000 test cases)

Test #6:

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

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:

-16364540619 27274234365
-407814367246 674462222753
507837871541 -836438847244
-36627896393 59936557734
-54800158259 89672986242
29167691456 -47397498616
124661740497 -201833294138
419921890206 -677293371300
-205443052656 330056051808
-1983420342 2975130513
1052833967326 -1677396490316
140764926884 ...

result:

ok T=49999 (49999 test cases)

Test #7:

score: -100
Runtime Error

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: