QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#591118 | #6812. Draw a triangle | Dixiky_215 | WA | 183ms | 3760kb | C++20 | 2.8kb | 2024-09-26 14:17:31 | 2024-09-26 14:17:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll =__int128;
// using ll = long long;
int t;
ll x,y,a,b,c;
ll d[15];
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);
}
}
void print(__int128 x)
{
if (!x)
{
putchar('0');
return;
}
if (x < 0) putchar('-'),x = -x;
print(x / 10);
putchar(x % 10 + '0');
}
ll num,minl,gcdk,ans_x,ans_y;
bool check(ll k,ll aa,ll bb)
{
if(k*gcdk==c) return 0;
ll xx=x*k,yy=y*k;
ll sumk,numk;
if(xx<-1e18)
{
sumk=-1e18-xx;
numk=sumk/aa;
if(!(sumk%aa==0))
{
if(aa<0) numk--;
else numk++;
}
xx+=numk*aa;
yy-=numk*bb;
}
if(xx>1e18)
{
sumk=xx-1e18;
numk=sumk/aa;
if(!(sumk%aa==0))
{
if(aa<0) numk--;
else numk++;
}
xx-=numk*aa;
yy+=numk*bb;
}
if(yy<-1e18)
{
sumk=-1e18-yy;
numk=sumk/bb;
if(!(sumk%bb==0))
{
if(bb<0) numk--;
else numk++;
}
xx-=numk*aa;
yy+=numk*bb;
}
if(yy>1e18)
{
sumk=yy-1e18;
numk=sumk/bb;
if(!(sumk%bb==0))
{
if(bb<0) numk--;
else numk++;
}
xx+=numk*aa;
yy-=numk*bb;
}
if(xx<=1e18&&yy<=1e18&&xx>=-1e18&&yy>=-1e18)
{
sumk=c-num*gcdk;
if(sumk<0) sumk=-sumk;
if(sumk<minl)
{
ans_x=xx;ans_y=yy;
minl=sumk;
}
return 1;
}
return 0;
}
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;
gcdk=__gcd(a,b);
ll numk=c/gcdk;
int tot=0;
d[++tot]=numk;
d[++tot]=numk-1;
d[++tot]=numk+1;
ex_gcd(a,b);
ll aa=b/gcdk,bb=a/gcdk;
num=0;minl=1e18;
for(int i=1;i<=tot;i++)
{
if(d[i]*gcdk==c) continue;
if(check(d[i],aa,bb))
{
continue;
}
}
if(numk<0)
{
ll l=-numk,r=0,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,aa,bb)) r=mid-1;
else l=mid+1;
}
}
else
{
ll l=0,r=numk,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,aa,bb)) l=mid+1;
else r=mid-1;
}
}
// cerr << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
assert(ans_x <= 1E18 and ans_x >= -1E18);
assert(ans_y >= -1E18 and ans_y <= 1E18);
cout<<format("{}", ans_x) <<" "<< format("{}", ans_y) <<'\n';
// cout<<ans_x<<" "<<ans_y<<"\n";
// print(ans_x);
// cout<<" ";
// print(ans_y);
// cout<<'\n';
}
return 0;
}
/*
1
464263912 393228064 151248499 729744865
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
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: 90ms
memory: 3732kb
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: 98ms
memory: 3620kb
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: 81ms
memory: 3732kb
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: 98ms
memory: 3568kb
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: 124ms
memory: 3624kb
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
Wrong Answer
time: 183ms
memory: 3536kb
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:
543983023148044288 999999999127912072 -999999997630395865 -252607027329252820 -999999999425886191 7740672728496480 999999998126298478 819971722560779467 -999999998196577470 -167664773605206235 999999999833018036 322525588547452949 -797579354108408967 -999999998762078921 -450485054651314378 -99999999...
result:
wrong answer wa on query #3 (test case 3)