Task: | 2021-luvut |
Sender: | nikolai2001 |
Submission time: | 2020-10-03 20:00:25 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 25 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 15 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
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 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#22 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#23 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#24 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#25 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#26 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#27 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#28 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#29 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#30 | WRONG ANSWER | 0.01 s | 3, 4 | details |
#31 | WRONG ANSWER | 0.01 s | 4 | details |
#32 | WRONG ANSWER | 0.01 s | 4 | details |
#33 | WRONG ANSWER | 0.01 s | 4 | details |
#34 | WRONG ANSWER | 0.01 s | 4 | details |
#35 | WRONG ANSWER | 0.01 s | 4 | details |
#36 | WRONG ANSWER | 0.01 s | 4 | details |
#37 | WRONG ANSWER | 0.01 s | 4 | details |
#38 | WRONG ANSWER | 0.01 s | 4 | details |
#39 | WRONG ANSWER | 0.01 s | 4 | details |
#40 | WRONG ANSWER | 0.01 s | 4 | details |
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: WRONG ANSWER
input |
---|
713294506861 |
correct output |
---|
20099206371786 |
user output |
---|
(empty) |
Test 22
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
191431126351 |
correct output |
---|
4193020274761 |
user output |
---|
(empty) |
Test 23
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
778422318223 |
correct output |
---|
20247733120134 |
user output |
---|
(empty) |
Test 24
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
931090767075 |
correct output |
---|
20691282041612 |
user output |
---|
(empty) |
Test 25
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
198806129726 |
correct output |
---|
4275365802196 |
user output |
---|
(empty) |
Test 26
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
724343399444 |
correct output |
---|
20128443204610 |
user output |
---|
(empty) |
Test 27
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
105064053560 |
correct output |
---|
2350677231115 |
user output |
---|
(empty) |
Test 28
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
236866700902 |
correct output |
---|
5872395029521 |
user output |
---|
(empty) |
Test 29
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
696349488695 |
correct output |
---|
20034225603103 |
user output |
---|
(empty) |
Test 30
Group: 3, 4
Verdict: WRONG ANSWER
input |
---|
30929267826 |
correct output |
---|
1205256095901 |
user output |
---|
(empty) |
Test 31
Group: 4
Verdict: WRONG ANSWER
input |
---|
576379198814226780 |
correct output |
---|
4185251600926331891 |
user output |
---|
(empty) |
Test 32
Group: 4
Verdict: WRONG ANSWER
input |
---|
291698664446913099 |
correct output |
---|
2280132983584730156 |
user output |
---|
(empty) |
Test 33
Group: 4
Verdict: WRONG ANSWER
input |
---|
693146378550043345 |
correct output |
---|
5270258230724009910 |
user output |
---|
(empty) |
Test 34
Group: 4
Verdict: WRONG ANSWER
input |
---|
685982323362439932 |
correct output |
---|
5236052744416920782 |
user output |
---|
(empty) |
Test 35
Group: 4
Verdict: WRONG ANSWER
input |
---|
838865925103308874 |
correct output |
---|
6800200426815679149 |
user output |
---|
(empty) |
Test 36
Group: 4
Verdict: WRONG ANSWER
input |
---|
766426223219980635 |
correct output |
---|
6112960212822572807 |
user output |
---|
(empty) |
Test 37
Group: 4
Verdict: WRONG ANSWER
input |
---|
652970397451919317 |
correct output |
---|
4923188580186259818 |
user output |
---|
(empty) |
Test 38
Group: 4
Verdict: WRONG ANSWER
input |
---|
188458586650539464 |
correct output |
---|
1903508375720755921 |
user output |
---|
(empty) |
Test 39
Group: 4
Verdict: WRONG ANSWER
input |
---|
157646989818721527 |
correct output |
---|
1525038392797601315 |
user output |
---|
(empty) |
Test 40
Group: 4
Verdict: WRONG ANSWER
input |
---|
898606361978236778 |
correct output |
---|
7326676702587314407 |
user output |
---|
(empty) |