CSES - Datatähti 2021 alku - Results
Submission details
Task:2021-luvut
Sender:nikolai2001
Submission time:2020-10-03 23:04:10 +0300
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED25
#4ACCEPTED50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3, 4details
#2ACCEPTED0.01 s1, 2, 3, 4details
#3ACCEPTED0.01 s1, 2, 3, 4details
#4ACCEPTED0.01 s1, 2, 3, 4details
#5ACCEPTED0.01 s1, 2, 3, 4details
#6ACCEPTED0.01 s1, 2, 3, 4details
#7ACCEPTED0.01 s1, 2, 3, 4details
#8ACCEPTED0.01 s1, 2, 3, 4details
#9ACCEPTED0.01 s1, 2, 3, 4details
#10ACCEPTED0.01 s1, 2, 3, 4details
#11ACCEPTED0.01 s2, 3, 4details
#12ACCEPTED0.01 s2, 3, 4details
#13ACCEPTED0.01 s2, 3, 4details
#14ACCEPTED0.01 s2, 3, 4details
#15ACCEPTED0.01 s2, 3, 4details
#16ACCEPTED0.01 s2, 3, 4details
#17ACCEPTED0.01 s2, 3, 4details
#18ACCEPTED0.01 s2, 3, 4details
#19ACCEPTED0.01 s2, 3, 4details
#20ACCEPTED0.01 s2, 3, 4details
#21ACCEPTED0.01 s3, 4details
#22ACCEPTED0.01 s3, 4details
#23ACCEPTED0.01 s3, 4details
#24ACCEPTED0.01 s3, 4details
#25ACCEPTED0.01 s3, 4details
#26ACCEPTED0.01 s3, 4details
#27ACCEPTED0.01 s3, 4details
#28ACCEPTED0.01 s3, 4details
#29ACCEPTED0.01 s3, 4details
#30ACCEPTED0.01 s3, 4details
#31ACCEPTED0.01 s4details
#32ACCEPTED0.01 s4details
#33ACCEPTED0.01 s4details
#34ACCEPTED0.01 s4details
#35ACCEPTED0.01 s4details
#36ACCEPTED0.01 s4details
#37ACCEPTED0.01 s4details
#38ACCEPTED0.01 s4details
#39ACCEPTED0.01 s4details
#40ACCEPTED0.01 s4details

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