QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #119027 | #6266. Good Bitstrings | pandapythoner# | 4.761905 | 99ms | 3844kb | C++14 | 4.2kb | 2023-07-04 19:09:26 | 2024-05-31 19:00:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define lll __int128_t
#define ll __int128_t
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
ostream &operator<<(ostream &out, __int128_t a){
out << (long long)a;
return out;
}
istream &operator>>(istream &in, __int128_t &a){
long long x;
in >> x;
a = x;
return in;
}
mt19937 rnd(234);
const lll inf = 3e18;
ll gcd(ll a, ll b){
while(a != 0){
b %= a;
swap(a, b);
}
return b;
}
struct bebra{
lll x, y;
bebra(){}
bebra(lll x, lll y) : x(x), y(y) {}
};
bool operator<(const bebra &a, const bebra &b){
return a.x * b.y < a.y * b.x;
}
bool operator<=(const bebra &a, const bebra &b){
return a.x * b.y <= a.y * b.x;
}
bebra operator+(const bebra &a, const bebra &b){
return bebra(a.x + b.x, a.y + b.y);
}
bebra operator-(const bebra &a, const bebra &b){
return bebra(a.x - b.x, a.y - b.y);
}
bebra operator*(const bebra &a, ll f){
return bebra(a.x * f, a.y * f);
}
bebra min(const bebra &a, const bebra &b){
if(a < b){
return a;
}
return b;
}
bebra max(const bebra &a, const bebra &b){
if(a < b){
return b;
}
return a;
}
ll solve_slow(ll a, ll b){
ll rs = 0;
bebra l(0, 1);
bebra r(inf, 1);
bebra opt(a, b);
bebra t(0, 0);
while(t.x < opt.x || t.y < opt.y){
if(t <= opt){
l = max(l, t);
t.x += 1;
auto f = t;
f.x += max((ll)0, (a / b) - 10);
if(f <= opt && !(l <= f && f < r)){
t = f;
}
} else{
r = min(r, t);
t.y += 1;
auto f = t;
f.y += max((ll)(0), (b / a) - 10);
if(opt < f && !(l <= f && f < r)){
t = f;
}
}
if(l <= t && t < r){
rs += 1;
}
}
return rs;
}
ll solve_high(bebra opt, bebra da, bebra db, ll da_cnt, ll db_cnt){
if(da_cnt == 0 || db_cnt == 0){
return da_cnt + db_cnt;
}
ll tr = da_cnt;
ll tl = -1;
while(tl + 1 < tr){
ll tm = (tl + tr) / 2;
if(da * tm + db <= opt){
tr = tm;
} else{
tl = tm;
}
}
ll t = tr;
ll new_da_cnt = db_cnt * t - da_cnt;
ll new_db_cnt = da_cnt - db_cnt * (t - 1);
bebra new_da = da * (t - 1) + db;
bebra new_db = da * (t - 1) + db;
ll rs = t;
rs += solve_high(opt, new_da, new_db, new_da_cnt, new_db_cnt);
return rs;
}
ll solve_high(ll a, ll b){
ll rs = 0;
ll tr = b;
ll tl = -1;
while(tl + 1 < tr){
ll tm = (tl + tr) / 2;
if(a * tm < b){
tl = tm;
} else{
tr = tm;
}
}
ll t = tr;
bebra da(1, t);
bebra db(1, t - 1);
bebra opt(a, b);
ll da_cnt = b - a * (t - 1);
ll db_cnt = a * t - b;
rs += solve_high(opt, da, db, da_cnt, db_cnt);
return rs;
}
ll solve(ll a, ll b){
if(a >= b){
return solve_slow(a, b);
}
ll rs = 0;
ll g = gcd(a, b);
rs += (g - 1) * 2;
a /= g;
b /= g;
rs += solve_high(a, b);
bebra l(0, 1);
bebra r(inf, 1);
bebra opt(a, b);
bebra t(0, 0);
while(t.x < opt.x || t.y < opt.y){
if(t <= opt){
l = max(l, t);
t.x += 1;
} else{
r = min(r, t);
t.y += 1;
}
if(opt < t && t < r){
rs += 1;
}
}
return rs;
}
int32_t main(){
if(0){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
if(0){
for(int i = 1; i <= 20; i += 1){
for(int j = 1; j <= 20; j += 1){
cout << std::setfill('0') << std::setw(2) << solve_slow(i, j) << " ";
}
cout << "\n";
}
}
int t;
cin >> t;
while(t--){
ll a, b;
cin >> a >> b;
assert(a <= 1e6 && b <= 1e6);
cout << solve(a, b) << "\n";
}
return 0;
}
/*
1
3 5
1
1 10000000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.7619
Accepted
time: 0ms
memory: 3504kb
input:
6 1 1 3 5 4 7 8 20 4 10 27 21
output:
1 5 7 10 6 13
result:
ok 6 lines
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3664kb
input:
10 85 13 71 66 28 66 29 71 96 63 38 31 17 68 36 58 36 4 63 33
output:
20 32 6232677355110279699 -8243677011835525398 27 16 36 6794461723947386772 15 17
result:
wrong answer 3rd lines differ - expected: '12', found: '6232677355110279699'
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 3824kb
input:
10 906 527 608 244 263 174 839 281 153 492 987 849 701 390 195 518 410 59 48 971
output:
23 42 50 80 4784640577594568034 31 28 -638110820187837670 30 7042744991481463112
result:
wrong answer 5th lines differ - expected: '19', found: '4784640577594568034'
Test #4:
score: 0
Wrong Answer
time: 99ms
memory: 3540kb
input:
10 147825 752503 960741 512108 83790 812992 328545 187606 182751 847169 818963 814953 706940 588194 981994 867047 248103 887086 501412 307158
output:
-8548404943152156948 68 4930052844354560953 156 -3583832510926770671 446 98 58 -5652849869808236855 80
result:
wrong answer 1st lines differ - expected: '88', found: '-8548404943152156948'
Test #5:
score: 0
Wrong Answer
time: 57ms
memory: 3796kb
input:
10 681404 333428 181650 647050 229028 687782 657455 275098 58398 718183 365468 24732 503720 479173 556360 20233 694125 203877 617154 619370
output:
95 1474425763289533670 6973174123720813782 54 -2895719806025176351 60 88 232 85 6952818883729460234
result:
wrong answer 2nd lines differ - expected: '141', found: '1474425763289533670'
Test #6:
score: 0
Wrong Answer
time: 59ms
memory: 3652kb
input:
10 404235 140228 733083 982834 604701 282642 318592 567367 846008 887551 189157 486078 378169 480062 408938 400339 571460 63131 310407 774407
output:
126 1590118912394897868 73 661153754184150500 574912648866663869 -6895480527489756491 8423197893602959999 129 178 3128787989133800414
result:
wrong answer 2nd lines differ - expected: '76', found: '1590118912394897868'
Test #7:
score: 0
Wrong Answer
time: 73ms
memory: 3844kb
input:
10 405251 463150 549854 432108 808582 443624 49509 52183 361422 938598 776469 624844 644904 51183 797412 713474 254877 321065 407957 46299
output:
5684115773473607992 108 66 46857 4773815605012750071 68 1172 21006 -7982962247996774727 68
result:
wrong answer 1st lines differ - expected: '1403', found: '5684115773473607992'
Test #8:
score: 0
Runtime Error
input:
10 663353776591300896 752020665300205866 943526717545269366 300114424946521359 230713640398918611 187010130850175053 118239107794585724 200822570858719651 723715408292350264 396254911812807997 704994781514794709 819815153424097044 296759919488427246 945994708325740034 927030050569777885 705328510163...
output:
result:
Test #9:
score: 0
Runtime Error
input:
10 263959270418486736 511944810471618212 719955631781742290 884235488590662642 911958183634412763 115875852572241461 882870749898577341 896059443335458468 497522514232414628 118311430658869194 953631769711592758 442130823895113645 516877924612139121 25792863217482507 670853595357487791 2210828766491...
output:
result:
Test #10:
score: 0
Runtime Error
input:
10 213394634718308650 567314195893526830 118718333481546670 984222666619725683 521169680133050475 379632545405725706 529433210710147101 666030768028277123 248727345489185865 923284915041497532 555027965912713377 803887041840034130 349121089908475057 822348686848065296 607629682756169018 642020332228...
output:
result:
Test #11:
score: 0
Runtime Error
input:
10 975925299289124420 60303066417239296 766474983477708842 896147119677109501 37292938145223081 40635895974758701 202932421403534375 409995075828727680 269767950521665045 612979965315330039 648872061480630731 203238724068557061 515872085687282128 932457502235646100 752197651492851645 591490401816131...
output:
result:
Test #12:
score: 0
Runtime Error
input:
10 834598416537042887 606025100334242999 320428844366792646 151368673495529221 842633031722285124 117239895104072930 625021458914788036 949669118025122161 486067279580042617 962611646795744707 819755947652456438 427518443947948205 34030594912010556 588251327521452796 272271618017091404 3833210869571...
output:
result:
Test #13:
score: 0
Runtime Error
input:
10 397193281271954503 61672130855956143 314492482187282527 654066356498811443 860745630666775130 569333826127128192 476297769468002128 352294660078528480 517761936701389633 534752001708683063 674202688566846814 64972659840190297 585800934763526200 297942354678997984 106591030796636628 31162653946104...
output:
result:
Test #14:
score: 0
Runtime Error
input:
10 208 565667425097819020 55 157321119038912352 316907676466271933 526 886500984850879616 22 299149363183826900 250 987113150500653689 61 159 670025876873085627 937166187092977629 764 874753340780245712 360 214921484777387769 800038093746969281
output:
result:
Test #15:
score: 0
Runtime Error
input:
10 166972379813397449 29 569066341265273971 539 506 968039217663997486 352182654566540336 969 121125523365707181 848 517719135958060282 793 738 784126291767169684 298484835440867551 651 603 365907938824348123 910247730461828965 805051032603503065
output:
result:
Test #16:
score: 0
Runtime Error
input:
10 553486341350597216 428 126 131864838709694768 488211818967176514 885 830 514390130212884291 548964274098890426 286 621370290006585458 204 257458383843435158 856 758 307692053217471135 439 434604040461145810 943589164042917917 667787609709087533
output:
result:
Test #17:
score: 0
Runtime Error
input:
10 320654112354370136 755 681 573231478158788514 375 855899714394872507 424 703958346499687295 143 455080993131748359 696 741114359393839020 332216328717809233 828 865773491535017948 263 480 875075196649813697 856882629296459076 668553697725070634
output:
result:
Test #18:
score: 0
Runtime Error
input:
10 450591848507395078 766 970498285745258150 887 867038654838117493 714 443 698101902806352737 387 449758430496187790 928952692836028738 882 378854113906172456 822 74 220142603208608569 442341090408329812 239 44892686468418987 155998982976513680
output:
result:
Test #19:
score: 0
Runtime Error
input:
10 531086304104565770 690 831665374188973520 355 247416398730469667 416 353278152789250259 494 679360140254826434 522 398 867668761409290914 747 460442302649347038 428 430798781926999813 660522762702293186 303 570848109939810343 23362523897201984
output:
result:
Test #20:
score: 0
Runtime Error
input:
10 686 681341882408235553 961632287055210199 674 908 102741991216141808 890 138144729944759257 419 829534498941150031 505 624489596307607256 871 609803422000753610 983533393633626409 998 212341556536790997 446 826239058008214318 864102713930342835
output:
result:
Test #21:
score: 0
Runtime Error
input:
10 976965156031061996 243 843847568805985436 621 573992055384105067 876 586 308437172337246069 448791804432291466 662 34 217523497482835562 619081882696846159 150 175189397944495946 977 654 836460039817622971 654824899345401176 269167483489754436