QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#660730	#1377. Liczba Potyczkowa	Starrykiller	10 ✓	1392ms	195200kb	C++23	1.4kb	2024-10-20 13:02:27	2024-10-20 13:02:28

Judging History

This is the latest submission verdict.

[2024-10-20 13:02:28]
Judged

Verdict: 10
Time: 1392ms
Memory: 195200kb

Show

[2024-10-20 13:02:27]
Submitted

answer

// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

template<typename L, typename R>
auto range(L l, R r) { return views::iota(l,r); }
auto rev=views::reverse;

template<typename T>
_GLIBCXX_ALWAYS_INLINE void chmax(T &a, T b) { a=max(a,b); }
template<typename T>
_GLIBCXX_ALWAYS_INLINE void chmin(T &a, T b) { a=min(a,b); }
#define int long long

int f[19][2520][512], a[19];

int dfs(int pos, int remainder, int st, bool lim, bool lead0) {
    if (!pos) {
        bool flag=1;
        for (auto j: range(0,9)) if (st>>j&1) 
            flag&=(remainder%(j+1))==0;
        return flag&&!lead0;
    }
    auto &now=f[pos][remainder][st];
    if (!lim&&!lead0&&~now) return now;
    int sum=0, up=lim?a[pos]:9;
    for (auto i: range(0,up+1)) {
        if (!lead0 && !i) continue;
        if (!i) sum+=dfs(pos-1,0,0,0,1);
        else sum+=dfs(pos-1,(remainder*10+i)%2520,st|(1<<(i-1)),lim&&i==up,0);
    }
    if (!lim&&!lead0) now=sum;
    return sum;
}

int solve(int x) {
    memset(f,-1,sizeof f);
    int len=0;
    while(x) a[++len]=x%10, x/=10;
    return dfs(len,0,0,1,1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
// int T; cin>>T;
int T=1;
while (T--) []{
    int l, r; cin>>l>>r;
    cout<<solve(r)-solve(l-1)<<'\n';
}();
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1

Accepted

Test #2:

score: 1

Accepted

time: 48ms

memory: 195080kb

input:

363144 876899

output:

result:

ok single line: '3411'

Test #3:

score: 1

Accepted

time: 32ms

memory: 195188kb

input:

340230 874639

output:

result:

ok single line: '3617'

Test #4:

score: 1

Accepted

time: 32ms

memory: 195080kb

input:

32302 781583

output:

result:

ok single line: '6807'

Test #5:

score: 1

Accepted

time: 33ms

memory: 195000kb

input:

88488 631722

output:

result:

ok single line: '5170'

Test #6:

score: 1

Accepted

time: 36ms

memory: 195112kb

input:

1 999999

output:

result:

ok single line: '9039'

Test #7:

score: 1

Accepted

time: 15ms

memory: 195076kb

input:

1 3

output:

result:

ok single line: '3'

Subtask #2:

score: 1

Accepted

Test #8:

score: 1

Accepted

time: 36ms

memory: 195080kb

input:

179929 564769

output:

result:

ok single line: '3604'

Test #9:

score: 1

Accepted

time: 28ms

memory: 195200kb

input:

31711 762820

output:

result:

ok single line: '6733'

Test #10:

score: 1

Accepted

time: 32ms

memory: 195084kb

input:

256077 909855

output:

result:

ok single line: '4760'

Test #11:

score: 1

Accepted

time: 20ms

memory: 195136kb

input:

1 1

output:

result:

ok single line: '1'

Test #12:

score: 1

Accepted

time: 47ms

memory: 195140kb

input:

999999 999999

output:

result:

ok single line: '1'

Test #13:

score: 1

Accepted

time: 28ms

memory: 195128kb

input:

7 777777

output:

result:

ok single line: '7647'

Subtask #3:

score: 1

Accepted

Test #14:

score: 1

Accepted

time: 1233ms

memory: 195076kb

input:

122131631847754346 122131631848754346

output:

result:

ok single line: '3453'

Test #15:

score: 1

Accepted

time: 1247ms

memory: 195068kb

input:

128432334112486543 128432334113486543

output:

result:

ok single line: '4125'

Test #16:

score: 1

Accepted

time: 1328ms

memory: 195128kb

input:

743991663373248757 743991663374248757

output:

result:

ok single line: '750'

Test #17:

score: 1

Accepted

time: 1391ms

memory: 195128kb

input:

479733667788711858 479733667789711858

output:

result:

ok single line: '540'

Test #18:

score: 1

Accepted

time: 1354ms

memory: 195068kb

input:

984884249721569329 984884249722569329

output:

result:

ok single line: '538'

Test #19:

score: 1

Accepted

time: 1301ms

memory: 195068kb

input:

842181284281211148 842181284282211148

output:

result:

ok single line: '4895'

Test #20:

score: 1

Accepted

time: 1191ms

memory: 195188kb

input:

111111111999111111 111111111999999999

output:

result:

ok single line: '3471'

Test #21:

score: 1

Accepted

time: 1338ms

memory: 195068kb

input:

739711793799117979 739711793800117960

output:

result:

ok single line: '909'

Test #22:

score: 1

Accepted

time: 1367ms

memory: 195124kb

input:

128188218820028888 128188218821028888

output:

result:

ok single line: '0'

Subtask #4:

score: 1

Accepted

Test #23:

score: 1

Accepted

time: 1302ms

memory: 195188kb

input:

741243251591748310 741243251592748310

output:

result:

ok single line: '0'

Test #24:

score: 1

Accepted

time: 1314ms

memory: 195080kb

input:

667248191241322668 667248191242322668

output:

result:

ok single line: '514'

Test #25:

score: 1

Accepted

time: 1317ms

memory: 195184kb

input:

690471708215144656 690471708215929947

output:

result:

ok single line: '0'

Test #26:

score: 1

Accepted

time: 1321ms

memory: 195116kb

input:

822917689289508021 822917689290278919

output:

result:

ok single line: '267'

Test #27:

score: 1

Accepted

time: 1392ms

memory: 195064kb

input:

887303869896247348 887303869896952857

output:

result:

ok single line: '0'

Test #28:

score: 1

Accepted

time: 1220ms

memory: 195072kb

input:

111111111111111111 111111111111999999

output:

result:

ok single line: '7356'

Test #29:

score: 1

Accepted

time: 1360ms

memory: 195064kb

input:

919319939131000000 919319939132000000

output:

result:

ok single line: '3496'

Test #30:

score: 1

Accepted

time: 1370ms

memory: 195112kb

input:

999999999998999599 999999999999999569

output:

result:

ok single line: '3473'

Test #31:

score: 1

Accepted

time: 1309ms

memory: 195128kb

input:

844748474847484872 844748474848484872

output:

result:

ok single line: '1274'

Subtask #5:

score: 1

Accepted

Test #32:

score: 1

Accepted

time: 360ms

memory: 195128kb

input:

812434728 993348936

output:

result:

ok single line: '338337'

Test #33:

score: 1

Accepted

time: 329ms

memory: 195136kb

input:

623332122 894148438

output:

result:

ok single line: '486872'

Test #34:

score: 1

Accepted

time: 348ms

memory: 195080kb

input:

407616095 921231288

output:

result:

ok single line: '830323'

Test #35:

score: 1

Accepted

time: 263ms

memory: 195092kb

input:

48017092 403952154

output:

result:

ok single line: '914030'

Test #36:

score: 1

Accepted

time: 190ms

memory: 195128kb

input:

1 888888888

output:

result:

ok single line: '1914280'

Test #37:

score: 1

Accepted

time: 179ms

memory: 195060kb

input:

1 999999999

output:

result:

ok single line: '2087730'

Test #38:

score: 1

Accepted

time: 360ms

memory: 195004kb

input:

888888888 999999998

output:

result:

ok single line: '173450'

Test #39:

score: 1

Accepted

time: 337ms

memory: 195084kb

input:

999999998 999999998

output:

result:

ok single line: '0'

Test #40:

score: 1

Accepted

time: 339ms

memory: 195128kb

input:

999999999 999999999

output:

result:

ok single line: '1'

Subtask #6:

score: 1

Accepted

Test #41:

score: 1

Accepted

time: 334ms

memory: 194996kb

input:

612898103 960422119

output:

result:

ok single line: '626204'

Test #42:

score: 1

Accepted

time: 311ms

memory: 195200kb

input:

307767660 774168456

output:

result:

ok single line: '836226'

Test #43:

score: 1

Accepted

time: 260ms

memory: 195128kb

input:

28144825 679458009

output:

result:

ok single line: '1453616'

Test #44:

score: 1

Accepted

time: 331ms

memory: 195128kb

input:

835232893 846324384

output:

result:

ok single line: '31546'

Test #45:

score: 1

Accepted

time: 190ms

memory: 195140kb

input:

1 999999998

output:

result:

ok single line: '2087729'

Test #46:

score: 1

Accepted

time: 357ms

memory: 195084kb

input:

888888888 888888888

output:

result:

ok single line: '1'

Test #47:

score: 1

Accepted

time: 347ms

memory: 195008kb

input:

888888888 999999999

output:

result:

ok single line: '173451'

Test #48:

score: 1

Accepted

time: 332ms

memory: 195072kb

input:

999999998 999999999

output:

result:

ok single line: '1'

Subtask #7:

score: 1

Accepted

Test #49:

score: 1

Accepted

time: 624ms

memory: 195064kb

input:

131718361824 249218928144

output:

98771504

result:

ok single line: '98771504'

Test #50:

score: 1

Accepted

time: 558ms

memory: 195192kb

input:

6261249492 441624183311

output:

351176580

result:

ok single line: '351176580'

Test #51:

score: 1

Accepted

time: 664ms

memory: 195068kb

input:

174446473236 631149932124

output:

274057587

result:

ok single line: '274057587'

Test #52:

score: 1

Accepted

time: 644ms

memory: 195188kb

input:

193314293316 538746482501

output:

236940170

result:

ok single line: '236940170'

Test #53:

score: 1

Accepted

time: 356ms

memory: 195096kb

input:

1 888888888888

output:

571424397

result:

ok single line: '571424397'

Test #54:

score: 1

Accepted

time: 355ms

memory: 195088kb

input:

1 999999999999

output:

631897069

result:

ok single line: '631897069'

Test #55:

score: 1

Accepted

time: 668ms

memory: 195076kb

input:

888888888888 999999999998

output:

60472672

result:

ok single line: '60472672'

Test #56:

score: 1

Accepted

time: 694ms

memory: 195184kb

input:

999999999998 999999999998

output:

result:

ok single line: '0'

Test #57:

score: 1

Accepted

time: 700ms

memory: 195064kb

input:

999999999999 999999999999

output:

result:

ok single line: '1'

Subtask #8:

score: 1

Accepted

Test #58:

score: 1

Accepted

time: 575ms

memory: 195084kb

input:

18819362664 912809626995

output:

556209369

result:

ok single line: '556209369'

Test #59:

score: 1

Accepted

time: 640ms

memory: 194996kb

input:

684391892328 713600370978

output:

13707982

result:

ok single line: '13707982'

Test #60:

score: 1

Accepted

time: 627ms

memory: 195136kb

input:

325274351910 419236628615

output:

69657750

result:

ok single line: '69657750'

Test #61:

score: 1

Accepted

time: 653ms

memory: 195112kb

input:

461249448192 484837848767

output:

20061229

result:

ok single line: '20061229'

Test #62:

score: 1

Accepted

time: 350ms

memory: 195132kb

input:

1 999999999998

output:

631897068

result:

ok single line: '631897068'

Test #63:

score: 1

Accepted

time: 704ms

memory: 194980kb

input:

888888888888 888888888888

output:

result:

ok single line: '1'

Test #64:

score: 1

Accepted

time: 679ms

memory: 195192kb

input:

888888888888 999999999999

output:

60472673

result:

ok single line: '60472673'

Test #65:

score: 1

Accepted

time: 672ms

memory: 195128kb

input:

999999999998 999999999999

output:

result:

ok single line: '1'

Subtask #9:

score: 1

Accepted

Test #66:

score: 1

Accepted

time: 1259ms

memory: 195068kb

input:

334337497414427632 563247418137418257

output:

16565546623710

result:

ok single line: '16565546623710'

Test #67:

score: 1

Accepted

time: 1287ms

memory: 195088kb

input:

222985405251591914 722886846342448367

output:

39144022836804

result:

ok single line: '39144022836804'

Test #68:

score: 1

Accepted

time: 1351ms

memory: 194996kb

input:

422758300424788386 991151974928048033

output:

40736108260842

result:

ok single line: '40736108260842'

Test #69:

score: 1

Accepted

time: 1382ms

memory: 195188kb

input:

246953072129180722 729186768937319112

output:

36372878116410

result:

ok single line: '36372878116410'

Test #70:

score: 1

Accepted

time: 687ms

memory: 195128kb

input:

1 888888888888888888

output:

75624142376194

result:

ok single line: '75624142376194'

Test #71:

score: 1

Accepted

time: 693ms

memory: 195068kb

input:

1 999999999999999999

output:

85088767344190

result:

ok single line: '85088767344190'

Test #72:

score: 1

Accepted

time: 1380ms

memory: 195080kb

input:

888888888888888888 999999999999999998

output:

9464624967996

result:

ok single line: '9464624967996'

Test #73:

score: 1

Accepted

time: 1372ms

memory: 195060kb

input:

999999999999999998 999999999999999998

output:

result:

ok single line: '0'

Test #74:

score: 1

Accepted

time: 1338ms

memory: 195108kb

input:

999999999999999999 999999999999999999

output:

result:

ok single line: '1'

Subtask #10:

score: 1

Accepted

Test #75:

score: 1

Accepted

time: 1374ms

memory: 195128kb

input:

714776677442744785 987126628667872896

output:

21760578239081

result:

ok single line: '21760578239081'

Test #76:

score: 1

Accepted

time: 1299ms

memory: 195200kb

input:

138884332647783744 238173673273438896

output:

9863665459360

result:

ok single line: '9863665459360'

Test #77:

score: 1

Accepted

time: 1272ms

memory: 195072kb

input:

214981933829884632 443134094745786315

output:

23694479164106

result:

ok single line: '23694479164106'

Test #78:

score: 1

Accepted

time: 1314ms

memory: 195116kb

input:

811832226268144129 999639293318282736

output:

17340049537490

result:

ok single line: '17340049537490'

Test #79:

score: 1

Accepted

time: 673ms

memory: 195004kb

input:

1 999999999999999998

output:

85088767344189

result:

ok single line: '85088767344189'

Test #80:

score: 1

Accepted

time: 1367ms

memory: 195012kb

input:

888888888888888888 888888888888888888

output:

result:

ok single line: '1'

Test #81:

score: 1

Accepted

time: 1334ms

memory: 195192kb

input:

888888888888888888 999999999999999999

output:

9464624967997

result:

ok single line: '9464624967997'

Test #82:

score: 1

Accepted

time: 1282ms

memory: 195080kb

input:

999999999999999998 999999999999999999

output:

result:

ok single line: '1'

Subtask #11:

score: 9.09091

Accepted