QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525495 | #6812. Draw a triangle | ucup-team3474 | TL | 24ms | 4068kb | C++20 | 2.1kb | 2024-08-20 17:08:43 | 2024-08-20 17:08:44 |
Judging History
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(_--){
__();
}
}
Details
Tip: Click on the bar to expand more detailed information
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 -...