Task: | 2021-luvut |
Sender: | nikolai2001 |
Submission time: | 2020-10-03 23:04:10 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 15 |
#3 | ACCEPTED | 25 |
#4 | ACCEPTED | 50 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#11 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#12 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#13 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#14 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#15 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#16 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#17 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#18 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#19 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#20 | ACCEPTED | 0.01 s | 2, 3, 4 | details |
#21 | ACCEPTED | 0.01 s | 3, 4 | details |
#22 | ACCEPTED | 0.01 s | 3, 4 | details |
#23 | ACCEPTED | 0.01 s | 3, 4 | details |
#24 | ACCEPTED | 0.01 s | 3, 4 | details |
#25 | ACCEPTED | 0.01 s | 3, 4 | details |
#26 | ACCEPTED | 0.01 s | 3, 4 | details |
#27 | ACCEPTED | 0.01 s | 3, 4 | details |
#28 | ACCEPTED | 0.01 s | 3, 4 | details |
#29 | ACCEPTED | 0.01 s | 3, 4 | details |
#30 | ACCEPTED | 0.01 s | 3, 4 | details |
#31 | ACCEPTED | 0.01 s | 4 | details |
#32 | ACCEPTED | 0.01 s | 4 | details |
#33 | ACCEPTED | 0.01 s | 4 | details |
#34 | ACCEPTED | 0.01 s | 4 | details |
#35 | ACCEPTED | 0.01 s | 4 | details |
#36 | ACCEPTED | 0.01 s | 4 | details |
#37 | ACCEPTED | 0.01 s | 4 | details |
#38 | ACCEPTED | 0.01 s | 4 | details |
#39 | ACCEPTED | 0.01 s | 4 | details |
#40 | ACCEPTED | 0.01 s | 4 | details |
Compiler report
input/code.cpp: In function 'uint64_t get1f(__int128 unsigned, __int128 unsigned, int)': input/code.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if(msd > wantedIndex) ~~~~^~~~~~~~~~~~~
Code
#include<bits/stdc++.h>using namespace std;// 0 - [n-1]uint64_t wantedIndex;void printBCD(__uint128_t bcd){char buf[33];char *c = buf + 32;do{*--c = '0' + (bcd & 0x0F);bcd >>= 4;}while(bcd > 0L);buf[32] = '\0';puts(c);//printf("%lx\n", bcd);}[[ noreturn ]] void returnBCD(__uint128_t bcd) {printBCD(bcd);exit(EXIT_SUCCESS);}uint64_t bcd(uint64_t n){uint64_t ret = 0;uint64_t sh = 0;while(n > 0){ret += (n % 10) << sh;n /= 10;sh += 4;}return ret;}uint64_t get1f(__uint128_t prefix, __uint128_t number, int nWidth){uint64_t nnumbers = (nWidth >> 2) * 9 + 10;if(wantedIndex >= nnumbers) return nnumbers;if(nWidth == 0){returnBCD(prefix << 4 | wantedIndex);}else{//int i = 0;char msd = number >> (nWidth - 4);if(msd > wantedIndex)returnBCD(prefix << 4 | wantedIndex << nWidth | number);wantedIndex -= msd;int nW = nWidth - 4;__uint128_t nMask = (1L << nW) - 1;__uint128_t pp = (prefix | number) & ~nMask;wantedIndex -= get1f( pp, number & nMask, nW);int i = msd + 1 + wantedIndex;assert(i < 10);returnBCD(prefix << 4 | i << nWidth | number);}}#define getxf(depth, previous, v0, v4, v8, v12, v16) \uint64_t get ## depth ## f(__uint128_t prefix, __uint128_t number, int nWidth){ \uint64_t nnumbers = v0; \if(nWidth >= 16) nnumbers = v16; \else if(nWidth >= 12) nnumbers = v12; \else if(nWidth >= 8) nnumbers = v8; \else if(nWidth >= 4) nnumbers = v4; \if(wantedIndex >= nnumbers) return nnumbers; \if(nWidth == 0){ \returnBCD(prefix << ((__uint128_t) depth ## L * 4) | bcd(wantedIndex) ); \}else{ \int i = 0; \char msd = number >> (nWidth - 4); \while(i < msd) \wantedIndex -= get ## previous ## f(prefix << 4 | i++ << nWidth, number, nWidth); \int nW = nWidth - 4; \int nMask = (1 << nW) - 1; \wantedIndex -= get ## depth ## f(prefix | msd << nW, number & nMask, nW); \i++; \while(i < 10) \wantedIndex -= get ## previous ## f(prefix << 4 | i++ << nWidth, number, nWidth); \} \throw "Should not return get2f"; \}getxf(2, 1, 100, 271, 523, 856, 1270)getxf(3, 2, 1000, 3439, 8146, 15850, 27280)getxf(4, 3, 10000, 40951, 114265, 256915, 502435)getxf(5, 4, 100000, 468559, 1496944, 3809179, 8331094)getxf(6, 5, 1000000, 5217031L, 18689527L, 52972138L, 127951984L)getxf(7, 6, 10000000L, 56953279L, 225159022L, 701908264L, 1853476120L)getxf(8, 7, 100000000L, 612579511L, 2639010709L, 8956185085L, 25637470165L)getxf(9, 8, 1000000000L, 6513215599L, 30264311980L, 110869977745L, 341607209230L)getxf(10, 9, 10000000000L, 68618940391L, 340997748211L, 1338827547916L, 4413292430986L)getxf(11, 10, 100000000000L, 717570463519L, 3786550197418L, 15835998128662L, 55555630007536L)getxf(12, 11, 1000000000000L, 7458134171671L, 41537085948433L, 184061069106391L, 684061739174215L)getxf(13, 12, 10000000000000L, 77123207545039L, 450956981080936L, 2107506603038455L, 8264062255606390L)getxf(14, 13, 100000000000000L, 794108867905351L, 4852721697633775L, 23820281124979870L, 98196841425437380L)getxf(15, 14, 1000000000000000L, 8146979811148159L, 51821475089852134L, 266204005214670964L, 1149975578043607384L)#define gX(depth, prev, big) \uint64_t getX(__uint128_t prefix, __uint128_t number, int nWidth){ \int i = 0; \\uint64_t n = 0; \\if(nWidth > 0){ \\\char msd = number >> (nWidth - 4); \\while(i < msd){ \wantedIndex = 0xFFFFFFFFFFFFFFFF;\n += get ## prev ## f(prefix << 4 | i << nWidth, number, nWidth); \i++; \} \\int nW = nWidth - 4; \int nMask = (1 << nW) - 1; \\n += getX(prefix | msd << nW, number & nMask, nW);\\i++;\while(i < 10){\wantedIndex = 0xFFFFFFFFFFFFFFFF;\n += get ## prev ## f(prefix << 4 | i << nWidth, number, nWidth);\i++;\}\\}else{\n+= big;\}\printf("%luL, ", n);\return n;\}\gX(15, 14, 1000000000000000L)int main(int argc, char *argv[]){if(argc < 2){cin >> wantedIndex;}else wantedIndex = atoll(argv[1]);wantedIndex--;//get1(0, 0x2021, 16, false);/*const char str[] = "2021";puts(str);*///get5f(0, 0x2021, 16);get15f(0, 0x2021, 16);//getX(0, 0x2048, 16);//getX(0, 0x2021, 16);//get2f(0, 0x2021, 16);}
Test details
Test 1
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
10 |
correct output |
---|
20214 |
user output |
---|
20214 |
Test 2
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
359 |
correct output |
---|
202661 |
user output |
---|
202661 |
Test 3
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
392 |
correct output |
---|
202819 |
user output |
---|
202819 |
Test 4
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
715 |
correct output |
---|
230721 |
user output |
---|
230721 |
Test 5
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
278 |
correct output |
---|
202219 |
user output |
---|
202219 |
Test 6
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
296 |
correct output |
---|
202318 |
user output |
---|
202318 |
Test 7
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
427 |
correct output |
---|
203214 |
user output |
---|
203214 |
Test 8
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
565 |
correct output |
---|
208212 |
user output |
---|
208212 |
Test 9
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
289 |
correct output |
---|
202311 |
user output |
---|
202311 |
Test 10
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
342 |
correct output |
---|
202581 |
user output |
---|
202581 |
Test 11
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
964486 |
correct output |
---|
182502018 |
user output |
---|
182502018 |
Test 12
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
110979 |
correct output |
---|
20296916 |
user output |
---|
20296916 |
Test 13
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
759149 |
correct output |
---|
126108721 |
user output |
---|
126108721 |
Test 14
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
234934 |
correct output |
---|
25023210 |
user output |
---|
25023210 |
Test 15
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
610310 |
correct output |
---|
120288133 |
user output |
---|
120288133 |
Test 16
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
956690 |
correct output |
---|
182027419 |
user output |
---|
182027419 |
Test 17
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
608459 |
correct output |
---|
120281827 |
user output |
---|
120281827 |
Test 18
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
944777 |
correct output |
---|
175260251 |
user output |
---|
175260251 |
Test 19
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
880780 |
correct output |
---|
152270421 |
user output |
---|
152270421 |
Test 20
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
418357 |
correct output |
---|
68202361 |
user output |
---|
68202361 |
Test 21
Group: 3, 4
Verdict: ACCEPTED
input |
---|
713294506861 |
correct output |
---|
20099206371786 |
user output |
---|
20099206371786 |
Test 22
Group: 3, 4
Verdict: ACCEPTED
input |
---|
191431126351 |
correct output |
---|
4193020274761 |
user output |
---|
4193020274761 |
Test 23
Group: 3, 4
Verdict: ACCEPTED
input |
---|
778422318223 |
correct output |
---|
20247733120134 |
user output |
---|
20247733120134 |
Test 24
Group: 3, 4
Verdict: ACCEPTED
input |
---|
931090767075 |
correct output |
---|
20691282041612 |
user output |
---|
20691282041612 |
Test 25
Group: 3, 4
Verdict: ACCEPTED
input |
---|
198806129726 |
correct output |
---|
4275365802196 |
user output |
---|
4275365802196 |
Test 26
Group: 3, 4
Verdict: ACCEPTED
input |
---|
724343399444 |
correct output |
---|
20128443204610 |
user output |
---|
20128443204610 |
Test 27
Group: 3, 4
Verdict: ACCEPTED
input |
---|
105064053560 |
correct output |
---|
2350677231115 |
user output |
---|
2350677231115 |
Test 28
Group: 3, 4
Verdict: ACCEPTED
input |
---|
236866700902 |
correct output |
---|
5872395029521 |
user output |
---|
5872395029521 |
Test 29
Group: 3, 4
Verdict: ACCEPTED
input |
---|
696349488695 |
correct output |
---|
20034225603103 |
user output |
---|
20034225603103 |
Test 30
Group: 3, 4
Verdict: ACCEPTED
input |
---|
30929267826 |
correct output |
---|
1205256095901 |
user output |
---|
1205256095901 |
Test 31
Group: 4
Verdict: ACCEPTED
input |
---|
576379198814226780 |
correct output |
---|
4185251600926331891 |
user output |
---|
4185251600926331891 |
Test 32
Group: 4
Verdict: ACCEPTED
input |
---|
291698664446913099 |
correct output |
---|
2280132983584730156 |
user output |
---|
2280132983584730156 |
Test 33
Group: 4
Verdict: ACCEPTED
input |
---|
693146378550043345 |
correct output |
---|
5270258230724009910 |
user output |
---|
5270258230724009910 |
Test 34
Group: 4
Verdict: ACCEPTED
input |
---|
685982323362439932 |
correct output |
---|
5236052744416920782 |
user output |
---|
5236052744416920782 |
Test 35
Group: 4
Verdict: ACCEPTED
input |
---|
838865925103308874 |
correct output |
---|
6800200426815679149 |
user output |
---|
6800200426815679149 |
Test 36
Group: 4
Verdict: ACCEPTED
input |
---|
766426223219980635 |
correct output |
---|
6112960212822572807 |
user output |
---|
6112960212822572807 |
Test 37
Group: 4
Verdict: ACCEPTED
input |
---|
652970397451919317 |
correct output |
---|
4923188580186259818 |
user output |
---|
4923188580186259818 |
Test 38
Group: 4
Verdict: ACCEPTED
input |
---|
188458586650539464 |
correct output |
---|
1903508375720755921 |
user output |
---|
1903508375720755921 |
Test 39
Group: 4
Verdict: ACCEPTED
input |
---|
157646989818721527 |
correct output |
---|
1525038392797601315 |
user output |
---|
1525038392797601315 |
Test 40
Group: 4
Verdict: ACCEPTED
input |
---|
898606361978236778 |
correct output |
---|
7326676702587314407 |
user output |
---|
7326676702587314407 |