QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#525505 | #6812. Draw a triangle | ucup-team3474 | AC ✓ | 35ms | 4120kb | C++20 | 3.0kb | 2024-08-20 17:17:57 | 2024-08-20 17:17:57 |
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;
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)