CSES - Datatähti 2021 alku - Results
Submission details
Task:2021-luvut
Sender:nikolai2001
Submission time:2020-10-03 20:00:25 +0300
Language:C++ (C++17)
Status:READY
Result:25
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#30
#40
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
#210.01 s3, 4details
#220.01 s3, 4details
#230.01 s3, 4details
#240.01 s3, 4details
#250.01 s3, 4details
#260.01 s3, 4details
#270.01 s3, 4details
#280.01 s3, 4details
#290.01 s3, 4details
#300.01 s3, 4details
#310.01 s4details
#320.01 s4details
#330.01 s4details
#340.01 s4details
#350.01 s4details
#360.01 s4details
#370.01 s4details
#380.01 s4details
#390.01 s4details
#400.01 s4details

Code

#include<bits/stdc++.h>

using namespace std;

// 0 - [n-1]
int wantedIndex;

void printBCD(uint64_t bcd){
    char buf[17];
    char *c = buf + 16;
    do{
        *--c = '0' + (bcd & 0x0F);
        bcd >>= 4;
    }while(bcd > 0L);

    buf[16] = '\0';

    puts(c);
}

[[ noreturn ]] void returnBCD(uint64_t bcd) {
    printBCD(bcd);

    exit(EXIT_SUCCESS);
}

uint64_t bcd(uint64_t n){
    int ret = 0;
    int sh = 0;
    while(n > 0){
        ret += (n % 10) << sh;
        n /= 10;
        sh += 4;
    }

    return ret;
}

uint64_t get1f(uint64_t prefix, uint64_t number, int nWidth){
    int 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;
        int nMask = (1 << nW) - 1;
        int 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(uint64_t prefix, uint64_t number, int nWidth){ \
    int 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 << (depth * 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)


uint64_t get1(uint64_t prefix, uint64_t number, int nWidth){
    int i = 0;

    uint64_t n = 0;

    if(nWidth != 0){
        char msd = number >> (nWidth - 4);

        while(i < msd){
            printBCD(prefix << 4 | i << nWidth | number);
            i++;
            n++;
        }

        int nW = nWidth - 4;
        int nMask = (1 << nW) - 1;
        int pp = (prefix | number) & ~nMask;

        n += get1( pp, number & nMask, nW);

        i++;
        while(i < 10){
            printBCD(prefix << 4 | i << nWidth | number);
            i++;
            n++;
        }
    }else{
        while(i < 10){
            printBCD(prefix << 4 | i);
            i++;
            n++;
        }
    }

    //printf("Get1 (%d): %lu\n", nWidth, n);

    return n;
}

uint64_t get2(uint64_t prefix, uint64_t number, int nWidth){
    int i = 0;

    uint64_t n = 0;

    if(nWidth > 0){

        // Most significant digit
        char msd = number >> (nWidth - 4);

        while(i < msd){
            n += get1(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

        int nW = nWidth - 4;
        int nMask = (1 << nW) - 1;

        n += get2(prefix | msd << nW, number & nMask, nW);

        i++;
        while(i < 10){
            n += get1(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

    }else{
        i = 0;
        while(1){
            printBCD(prefix << 8 | i);
            if( (++i & 0x0F) <= 9){
                continue;
            }

            i+= 0x10 - 10;
            if(i >= 0xA0) break;
        }
        n+= 100;
    }

    //printf("Get2 (%d): %lu\n", nWidth, n);
    return n;
}

uint64_t get3(uint64_t prefix, uint64_t number, int nWidth){
    int i = 0;

    uint64_t n = 0;

    if(nWidth > 0){

        // Most significant digit
        char msd = number >> (nWidth - 4);

        while(i < msd){
            wantedIndex = 0xFFFFFFF;
            n += get2(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

        int nW = nWidth - 4;
        int nMask = (1 << nW) - 1;

        n += get3(prefix | msd << nW, number & nMask, nW);

        i++;
        while(i < 10){
            wantedIndex = 0xFFFFFFF;
            n += get2(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

    }else{
        i = 0;
        while(1){
            printBCD(prefix << 12 | i);
            if( (++i & 0x0F) <= 9){
                continue;
            }

            i+= 0x10 - 10;
            if( (i & 0xFF) < 0xA0) continue;
            i+= 0x100 - 0xA0;
            if(i >= 0xA00) break;
        }
        n+= 1000;
    }
    //printf("Get3 (%d): %lu\n", nWidth, n);
    return n;
}

int depth = 1;

uint64_t get4(uint64_t prefix, uint64_t number, int nWidth){
    int i = 0;

    uint64_t n = 0;

    if(nWidth > 0){

        // Most significant digit
        char msd = number >> (nWidth - 4);

        while(i < msd){
            n += get3(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

        int nW = nWidth - 4;
        int nMask = (1 << nW) - 1;

        depth++;
        n += get4(prefix | msd << nW, number & nMask, nW);
        depth--;

        i++;
        while(i < 10){
            n += get3(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

    }else{
        i = 0;
        while(1){
            printBCD(prefix << 16 | i);
            if( (++i & 0x0F) <= 9){
                continue;
            }

            i+= 0x10 - 10;
            if( (i & 0xFF) < 0xA0) continue;
            i+= 0x100 - 0xA0;
            if( (i & 0xFFF) < 0xA00) continue;
            i+= 0x1000 - 0xA00;
            if(i >= 0xA000) break;
        }
        n+= 10000;
    }
    //printf("Get4 (%d): %lu\n", nWidth, n);
    return n;
}

uint64_t get5(uint64_t prefix, uint64_t number, int nWidth){
    int i = 0;

    uint64_t n = 0;

    if(nWidth > 0){

        // Most significant digit
        char msd = number >> (nWidth - 4);

        while(i < msd){
            n += get4(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

        int nW = nWidth - 4;
        int nMask = (1 << nW) - 1;

        n += get5(prefix | msd << nW, number & nMask, nW);

        i++;
        while(i < 10){
            n += get4(prefix << 4 | i << nWidth, number, nWidth);
            i++;
        }

    }else{
        i = 0;
        while(1){
            printBCD(prefix << 16 | i);
            if( (++i & 0x0F) <= 9){
                continue;
            }

            i+= 0x10 - 10;
            if( (i & 0xFF) < 0xA0) continue;
            i+= 0x100 - 0xA0;
            if( (i & 0xFFF) < 0xA00) continue;
            i+= 0x1000 - 0xA00;
            if(i >= 0xA000) break;
        }
        n+= 100000;
    }
    //printf("Get5 (%d): %lu\n", nWidth, n);
    return n;
}

int main(int argc, char *argv[]){
    if(argc < 2){
        cin >> wantedIndex;
        
    }else wantedIndex = atoi(argv[1]);

    wantedIndex--;

    //get1(0, 0x2021, 16, false);

    /*const char str[] = "2021";
    puts(str);*/

    get5f(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:

input
713294506861

correct output
20099206371786

user output
(empty)

Test 22

Group: 3, 4

Verdict:

input
191431126351

correct output
4193020274761

user output
(empty)

Test 23

Group: 3, 4

Verdict:

input
778422318223

correct output
20247733120134

user output
(empty)

Test 24

Group: 3, 4

Verdict:

input
931090767075

correct output
20691282041612

user output
(empty)

Test 25

Group: 3, 4

Verdict:

input
198806129726

correct output
4275365802196

user output
(empty)

Test 26

Group: 3, 4

Verdict:

input
724343399444

correct output
20128443204610

user output
(empty)

Test 27

Group: 3, 4

Verdict:

input
105064053560

correct output
2350677231115

user output
(empty)

Test 28

Group: 3, 4

Verdict:

input
236866700902

correct output
5872395029521

user output
(empty)

Test 29

Group: 3, 4

Verdict:

input
696349488695

correct output
20034225603103

user output
(empty)

Test 30

Group: 3, 4

Verdict:

input
30929267826

correct output
1205256095901

user output
(empty)

Test 31

Group: 4

Verdict:

input
576379198814226780

correct output
4185251600926331891

user output
(empty)

Test 32

Group: 4

Verdict:

input
291698664446913099

correct output
2280132983584730156

user output
(empty)

Test 33

Group: 4

Verdict:

input
693146378550043345

correct output
5270258230724009910

user output
(empty)

Test 34

Group: 4

Verdict:

input
685982323362439932

correct output
5236052744416920782

user output
(empty)

Test 35

Group: 4

Verdict:

input
838865925103308874

correct output
6800200426815679149

user output
(empty)

Test 36

Group: 4

Verdict:

input
766426223219980635

correct output
6112960212822572807

user output
(empty)

Test 37

Group: 4

Verdict:

input
652970397451919317

correct output
4923188580186259818

user output
(empty)

Test 38

Group: 4

Verdict:

input
188458586650539464

correct output
1903508375720755921

user output
(empty)

Test 39

Group: 4

Verdict:

input
157646989818721527

correct output
1525038392797601315

user output
(empty)

Test 40

Group: 4

Verdict:

input
898606361978236778

correct output
7326676702587314407

user output
(empty)