QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#269312 | #6812. Draw a triangle | ucup-team1001# | AC ✓ | 54ms | 3832kb | C++23 | 2.1kb | 2023-11-29 15:04:31 | 2023-11-29 15:04:31 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define x1 jdfhnskjsdnbflj
#define y1 bhfgrbsw
#define int long long
int exgcd(int a, int b, __int128 &x, __int128 &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
__int128 temp = x;
x = y;
y = temp - a / b * y;
return d;
}
void solve() {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int a = y2 - y1;
int b = x1 - x2;
int c = x2 * y1 - y2 * x1;
__int128 x, y;
int d = exgcd(a, b, x, y);
// cout << x << " " << y << endl;
// cout << c << " " << d << endl;
x *= (-c + d) / d;
y *= (-c + d) / d;
// cout << x << " " << y << endl;
auto ceil = [](__int128 a, __int128 b) -> __int128 {
return (a + b - 1) / b;
};
const __int128 ma = 1000'000'000'000'000'000ll;
if (x > ma) {
if (b > 0) {
__int128 n = ceil(x - ma, b);
x -= n * b;
y += n * a;
} else {
__int128 n = ceil(x - ma, -b);
x += n * b;
y -= n * a;
}
}
if (x < -ma) {
if (b > 0) {
__int128 n = ceil(-ma - x, b);
x += n * b;
y -= n * a;
} else {
__int128 n = ceil(-ma - x, -b);
x -= n * b;
y += n * a;
}
}
if (y > ma) {
if (a > 0) {
__int128 n = ceil(y - ma, a);
x += n * b;
y -= n * a;
} else {
__int128 n = ceil(y - ma, -a);
x -= n * b;
y += n * a;
}
}
if (y < -ma) {
if (a > 0) {
__int128 n = ceil(-ma - y, a);
x -= n * b;
y += n * a;
} else {
__int128 n = ceil(-ma - y, -a);
x += n * b;
y -= n * a;
}
}
cout << (int)x << " " <<(int) y << endl;
}
signed main() {
IOS
int t = 1;
cin >> t;
while (t--)solve();
}
//1
//999999999 0
//0 499999999
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
3 1 0 1 4 0 1 0 9 0 0 2 2
output:
2 0 1 0 0 1
result:
ok T=3 (3 test cases)
Test #2:
score: 0
Accepted
time: 36ms
memory: 3560kb
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 13723647137 13723647137 10625410771 10625410771 -2267030938412 -2239717312648 -1090149184320 -1072566132960 8539561213 8539561213 -511914166638 -499725734099 424314498206 412417830032 319508495863 309201770190 -578593658835 -557743436895 735414464 735414464 -475560039227 -454656301239 3...
result:
ok T=50000 (50000 test cases)
Test #3:
score: 0
Accepted
time: 24ms
memory: 3584kb
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:
-383732562 -767465124 1437479154 2395798590 -278763942756 -461032674558 172989475041 284923841244 8817758411 14429059218 75677936158 123836622804 -78816354856 -128076576641 -205662025800 -332976613200 241510584310 389533200500 938919977092 1508428815656 -271531094 -407296641 -696880821473 -111028469...
result:
ok T=50000 (50000 test cases)
Test #4:
score: 0
Accepted
time: 40ms
memory: 3524kb
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 -7078219245 -35391096225 -10575123719 -52875618595 -47447055454 -234444274008 81478131720 400600814290 531770561 2658852805 -48464548072 -236264671851 -90946206673 -441738718126 -19983343602 -96586160743 139544142287 672349049201 -1457322350 -7286611750 -89345914470 -426874924690 1265746...
result:
ok T=50000 (50000 test cases)
Test #5:
score: 0
Accepted
time: 40ms
memory: 3532kb
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:
-15009662161 75048310805 1038075557 -5190377785 179681954869 -887840247588 76990356 -378535917 -461813023 2309065115 9525883056 -46438679898 67744093837 -329042741494 33009261084 -159544761906 -174847788115 842448433645 -2199586039 10997930195 -62832387006 300199182362 23538925692 -111809897037 -361...
result:
ok T=50000 (50000 test cases)
Test #6:
score: 0
Accepted
time: 20ms
memory: 3616kb
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:
-16364540625 27274234375 -407814367298 674462222839 507837871507 -836438847188 -36627896371 59936557698 -54800158281 89672986278 29167691472 -47397498642 124661740539 -201833294206 419921890268 -677293371400 -205443052534 330056051612 -1983420338 2975130507 1052833967444 -1677396490504 140764926942 ...
result:
ok T=49999 (49999 test cases)
Test #7:
score: 0
Accepted
time: 46ms
memory: 3560kb
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:
543983023286575242 999999999382572508 -999999999735258545 -252607027860955926 -999999999841925448 7740673117702878 999999999927240046 819971723858782146 -999999999609929684 -167664773842175614 999999999931812312 322525588579316631 -797579353698884645 -999999998248619891 -450485054709837355 -99999999...
result:
ok T=50000 (50000 test cases)
Test #8:
score: 0
Accepted
time: 35ms
memory: 3828kb
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 667306234792890259 -999999999435044924 769937747377379950 999999999402832053 999999999941869273 102986803738631652 573074169710045548 -999999999587526693 -290460098759920663 -999999999469476448 673996582308644782 -999999999532825380 -716056783903600516 -9999999...
result:
ok T=50000 (50000 test cases)
Test #9:
score: 0
Accepted
time: 31ms
memory: 3760kb
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:
999999999862352364 488413458698726811 999999999428004214 553964586576344582 -999999999570594971 -315025249393246397 999999999945161807 581346867062012418 999999999910560031 660019266541889838 999999999392591147 630248394533687912 -999999999694137438 117754346074022186 -843929568262775150 99999999894...
result:
ok T=50000 (50000 test cases)
Test #10:
score: 0
Accepted
time: 44ms
memory: 3748kb
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:
937907383232048360 999999999761055869 500544124678657968 999999999863903423 152046808192596331 999999999828287825 -999999999968557242 13424931744783487 -245737391395780671 -999999999294998042 -231191815212939544 999999999937735543 -999999999513972007 -573959889679767829 -999999999338143338 -61894776...
result:
ok T=50000 (50000 test cases)
Test #11:
score: 0
Accepted
time: 23ms
memory: 3532kb
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:
200697523547190454 999999999165032019 999999999464792817 494158637293254489 -999999999457123181 3808495720275819 170796980516062041 999999999295062066 999999999982127149 -331032284373155896 999999999709427514 469166346451988220 858922231955533292 -999999999914750444 999999999665688650 -1185624899161...
result:
ok T=50000 (50000 test cases)
Test #12:
score: 0
Accepted
time: 43ms
memory: 3528kb
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:
479403977356557283 -999999999733441009 -11752057409716182 999999999365536819 -999999999212232992 635477861056494815 17948082140803980 999999999800728624 999999999960277791 -658247568971994097 889235605623094957 -999999999820079923 999999999816524476 361005428005184055 705341985526712069 999999999613...
result:
ok T=50000 (50000 test cases)
Test #13:
score: 0
Accepted
time: 40ms
memory: 3624kb
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:
999999999566732019 838539797022838312 -999999998727847284 110452237744504319 -423162297262445121 999999999950049703 999999999983913720 -133828106929336589 -999999999798118392 -705196195362797734 -65926854992597928 -999999999495671724 -999999999702297403 582844185987464758 986009195748680989 99999999...
result:
ok T=50000 (50000 test cases)
Test #14:
score: 0
Accepted
time: 49ms
memory: 3624kb
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:
999999999029528200 -363519222255770196 424190323848958477 999999999417246725 999999998968408435 76145828132019266 -235549142394575215 999999998942546497 999999999562414790 822807904609566890 655442889780494700 -999999999856296406 370259931314659360 -999999998790691376 -601250908782151217 -9999999991...
result:
ok T=50000 (50000 test cases)
Test #15:
score: 0
Accepted
time: 43ms
memory: 3832kb
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:
999999999838916668 -445550930723009786 602828433672441 999999999847698072 -145574898956145123 -999999998752940548 999999999861649195 376930736914804048 -999999999731822542 158767833158332752 -176554411356033249 -999999999281610846 256785196741975860 -999999999574501448 -205149814553852225 -999999999...
result:
ok T=50000 (50000 test cases)
Test #16:
score: 0
Accepted
time: 32ms
memory: 3528kb
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 -388877351158707435 999999999369959425 -803667730740336777 999999999109589563 -999999999993971668 -18506714198320844 999999999833538239 31976046...
result:
ok T=50000 (50000 test cases)
Test #17:
score: 0
Accepted
time: 28ms
memory: 3784kb
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:
-587513256346173957 -999999999160822060 668332514816083814 -999999999524061892 205585094461305148 -999999998705439632 -459398187067296713 -999999999821732660 999999999932846017 -185325822339665227 999999999231436102 -867394525880525864 -999999999522617125 616003959210933099 39348025687609234 9999999...
result:
ok T=50000 (50000 test cases)
Test #18:
score: 0
Accepted
time: 54ms
memory: 3620kb
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 343653450443143708 -999999999495616166 141786473897742612 -999999999596156836 -999999999222238424 755078281740917518 861044182671116434 999999998950478470 999999999014901769 721474828389761631 -999999999598369466 -901419471267510853 -999999999777547434 4554518...
result:
ok T=50000 (50000 test cases)
Test #19:
score: 0
Accepted
time: 38ms
memory: 3608kb
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:
999999999346943987 234248354728430606 208157512721773950 999999999891690257 691301214918648255 999999999417039525 -999999999635675656 244362943806420417 999999999550378450 657025675676517908 -673847597563659844 -999999998956858524 793014963234944439 -999999999202717471 -999999999599981638 8468095068...
result:
ok T=50000 (50000 test cases)
Test #20:
score: 0
Accepted
time: 23ms
memory: 3628kb
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 591976373143001180 -999999999493643587 30264892022949361 -999999999682621818 -7674081557131299 -999999999042673162 999999998676786234 192094630965435928 -999999998981925608 -432046702093986899 -343351647605681988 -999999999...
result:
ok T=50000 (50000 test cases)
Test #21:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
3 -1000000000 -1000000000 1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000
output:
0 1 0 -999999999 -999999999 0
result:
ok T=3 (3 test cases)