CSES - Datatähti 2020 alku - Results
Submission details
Task:Lukuvälit
Sender:eliaskosunen
Submission time:2019-10-02 00:40:23 +0300
Language:C++ (C++17)
Status:READY
Result:36
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED24
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s1, 2, 3details
#12ACCEPTED0.01 s1, 2, 3details
#13ACCEPTED0.05 s2, 3details
#14ACCEPTED0.03 s2, 3details
#15ACCEPTED0.05 s2, 3details
#16ACCEPTED0.04 s2, 3details
#17ACCEPTED0.03 s2, 3details
#18ACCEPTED0.05 s2, 3details
#19ACCEPTED0.01 s2, 3details
#20ACCEPTED0.01 s2, 3details
#21--3details
#22--3details
#23--3details
#24--3details
#25ACCEPTED0.21 s3details
#26--3details
#27ACCEPTED0.11 s3details
#28ACCEPTED0.11 s3details

Compiler report

input/code.cpp: In member function 'i64 pretend_binary::as_integer()':
input/code.cpp:116:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (u64 k = 0; k < 64 - __builtin_clzll(value); ++k) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

// Lukuvälit
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;
constexpr i64 round_up_10(i64 i)
{
return ((i + 10ll - 1ll) / 10ll) * 10ll;
}
static constexpr i64 precalc[] = {
0, 1, 10, 11, 100, 101, 110,
111, 1000, 1001, 1010, 1011, 1100, 1101,
1110, 1111, 10000, 10001, 10010, 10011, 10100,
10101, 10110, 10111, 11000, 11001, 11010, 11011,
11100, 11101, 11110, 11111, 100000, 100001, 100010,
100011, 100100, 100101, 100110, 100111, 101000, 101001,
101010, 101011, 101100, 101101, 101110, 101111, 110000,
110001, 110010, 110011, 110100, 110101, 110110, 110111,
111000, 111001, 111010, 111011, 111100, 111101, 111110,
111111, 1000000, 1000001, 1000010, 1000011, 1000100, 1000101,
1000110, 1000111, 1001000, 1001001, 1001010, 1001011, 1001100,
1001101, 1001110, 1001111, 1010000, 1010001, 1010010, 1010011,
1010100, 1010101, 1010110, 1010111, 1011000, 1011001, 1011010,
1011011, 1011100, 1011101, 1011110, 1011111, 1100000, 1100001,
1100010, 1100011, 1100100, 1100101, 1100110, 1100111, 1101000,
1101001, 1101010, 1101011, 1101100, 1101101, 1101110, 1101111,
1110000, 1110001, 1110010, 1110011, 1110100, 1110101, 1110110,
1110111, 1111000, 1111001, 1111010, 1111011, 1111100, 1111101,
1111110, 1111111, 10000000, 10000001, 10000010, 10000011, 10000100,
10000101, 10000110, 10000111, 10001000, 10001001, 10001010, 10001011,
10001100, 10001101, 10001110, 10001111, 10010000, 10010001, 10010010,
10010011, 10010100, 10010101, 10010110, 10010111, 10011000, 10011001,
10011010, 10011011, 10011100, 10011101, 10011110, 10011111, 10100000,
10100001, 10100010, 10100011, 10100100, 10100101, 10100110, 10100111,
10101000, 10101001, 10101010, 10101011, 10101100, 10101101, 10101110,
10101111, 10110000, 10110001, 10110010, 10110011, 10110100, 10110101,
10110110, 10110111, 10111000, 10111001, 10111010, 10111011, 10111100,
10111101, 10111110, 10111111, 11000000, 11000001, 11000010, 11000011,
11000100, 11000101, 11000110, 11000111, 11001000, 11001001, 11001010,
11001011, 11001100, 11001101, 11001110, 11001111, 11010000, 11010001,
11010010, 11010011, 11010100, 11010101, 11010110, 11010111, 11011000,
11011001, 11011010, 11011011, 11011100, 11011101, 11011110, 11011111,
11100000, 11100001, 11100010, 11100011, 11100100, 11100101, 11100110,
11100111, 11101000, 11101001, 11101010, 11101011, 11101100, 11101101,
11101110, 11101111, 11110000, 11110001, 11110010, 11110011, 11110100,
11110101, 11110110, 11110111, 11111000, 11111001, 11111010, 11111011,
11111100, 11111101, 11111110, 11111111, 100000000, 100000001, 100000010,
100000011, 100000100, 100000101, 100000110, 100000111, 100001000, 100001001,
100001010, 100001011, 100001100, 100001101, 100001110, 100001111, 100010000,
100010001, 100010010, 100010011, 100010100, 100010101, 100010110, 100010111,
100011000, 100011001, 100011010, 100011011, 100011100, 100011101, 100011110,
100011111, 100100000, 100100001, 100100010, 100100011, 100100100, 100100101,
100100110, 100100111, 100101000, 100101001, 100101010, 100101011, 100101100,
100101101, 100101110, 100101111, 100110000, 100110001, 100110010, 100110011,
100110100, 100110101, 100110110, 100110111, 100111000, 100111001, 100111010,
100111011, 100111100, 100111101, 100111110, 100111111, 101000000, 101000001,
101000010, 101000011, 101000100, 101000101, 101000110, 101000111, 101001000,
101001001, 101001010, 101001011, 101001100, 101001101, 101001110, 101001111,
101010000, 101010001, 101010010, 101010011, 101010100, 101010101, 101010110,
101010111, 101011000, 101011001, 101011010, 101011011, 101011100, 101011101,
101011110, 101011111, 101100000, 101100001, 101100010, 101100011, 101100100,
101100101, 101100110, 101100111, 101101000, 101101001, 101101010, 101101011,
101101100, 101101101, 101101110, 101101111, 101110000, 101110001, 101110010,
101110011, 101110100, 101110101, 101110110, 101110111, 101111000, 101111001,
101111010, 101111011, 101111100, 101111101, 101111110, 101111111, 110000000,
110000001, 110000010, 110000011, 110000100, 110000101, 110000110, 110000111,
110001000, 110001001, 110001010, 110001011, 110001100, 110001101, 110001110,
110001111, 110010000, 110010001, 110010010, 110010011, 110010100, 110010101,
110010110, 110010111, 110011000, 110011001, 110011010, 110011011, 110011100,
110011101, 110011110, 110011111, 110100000, 110100001, 110100010, 110100011,
110100100, 110100101, 110100110, 110100111, 110101000, 110101001, 110101010,
110101011, 110101100, 110101101, 110101110, 110101111, 110110000, 110110001,
110110010, 110110011, 110110100, 110110101, 110110110, 110110111, 110111000,
110111001, 110111010, 110111011, 110111100, 110111101, 110111110, 110111111,
111000000, 111000001, 111000010, 111000011, 111000100, 111000101, 111000110,
111000111, 111001000, 111001001, 111001010, 111001011, 111001100, 111001101,
111001110, 111001111, 111010000, 111010001, 111010010, 111010011, 111010100,
111010101, 111010110, 111010111, 111011000, 111011001, 111011010, 111011011,
111011100, 111011101, 111011110, 111011111, 111100000, 111100001, 111100010,
111100011, 111100100, 111100101, 111100110, 111100111, 111101000, 111101001,
111101010, 111101011, 111101100, 111101101, 111101110, 111101111, 111110000,
111110001, 111110010, 111110011, 111110100, 111110101, 111110110, 111110111,
111111000, 111111001, 111111010, 111111011, 111111100, 111111101, 111111110,
111111111};
template <typename T>
constexpr T power_of_10(T x)
{
T i = 1;
for (T j = 1; j <= x; j++) {
i *= 10;
}
return i;
}
struct pretend_binary {
// store in decimal
u64 value{0};
// if value == 3, returns 11 in base 10,
// which looks like 0b11
i64 as_integer()
{
i64 val{0};
for (u64 k = 0; k < 64 - __builtin_clzll(value); ++k) {
auto mask = 1 << k;
auto masked = value & mask;
val += (masked >> k) * power_of_10(k);
}
return val;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<i64, i64>> vec(n);
i64 largest_end{0};
for (int i = 0; i < n; ++i) {
i64 a, b;
cin >> a >> b;
vec[i] = make_pair(a, b);
if (b > largest_end) {
largest_end = b;
}
}
set<i64> cache{begin(precalc), end(precalc)};
if (largest_end >= 111'111'111) {
pretend_binary bin{512};
i64 i = bin.as_integer();
for (; i <= largest_end; ++bin.value) {
i = bin.as_integer();
cache.insert(i);
}
}
for (auto& p : vec) {
auto begin = cache.lower_bound(p.first);
auto end = cache.upper_bound(p.second);
cout << distance(begin, end) << '\n';
}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
4
0 10
1 5
3 4
11 11

correct output
3
1
0
1

user output
3
1
0
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
0 0

correct output
1

user output
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
1000 1000

correct output
1

user output
1

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
16
0 0
0 1
0 2
1 1
...

correct output
1
2
2
1
1
...

user output
1
2
2
1
1
...

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
9
0 0
0 1
0 10
0 11
...

correct output
1
2
3
4
5
...

user output
1
2
3
4
5
...

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
0 1000
0 1000
0 1000
0 1000
...

correct output
9
9
9
9
9
...

user output
9
9
9
9
9
...
Truncated

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
100 111
0 101
1 10
10 110
...

correct output
4
6
2
5
8
...

user output
4
6
2
5
8
...
Truncated

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
480 564
753 988
479 909
32 973
...

correct output
0
0
0
4
0
...

user output
0
0
0
4
0
...
Truncated

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
98 111
8 111
98 111
111 113
...

correct output
4
6
4
1
7
...

user output
4
6
4
1
7
...
Truncated

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
0 0
1 1
2 2
3 3
...

correct output
1
1
0
0
0
...

user output
1
1
0
0
0
...
Truncated

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
0 1000
0 999
1 1000
0 998
...

correct output
9
8
8
8
7
...

user output
9
8
8
8
7
...
Truncated

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
0 1000

correct output
9

user output
9

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
100000
0 100000
0 100000
0 100000
0 100000
...

correct output
33
33
33
33
33
...

user output
33
33
33
33
33
...
Truncated

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
100000
86042 98295
30077 80920
45856 67174
3890 60412
...

correct output
0
0
0
16
0
...

user output
0
0
0
16
0
...
Truncated

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
100000
11 10000
1111 11000
1011 1100
1110 1111
...

correct output
14
10
2
2
8
...

user output
14
10
2
2
8
...
Truncated

Test 16

Group: 2, 3

Verdict: ACCEPTED

input
100000
9 9999
1109 1110
112 1012
11098 11101
...

correct output
14
1
4
2
6
...

user output
14
1
4
2
6
...
Truncated

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
100000
0 0
1 1
2 2
3 3
...

correct output
1
1
0
0
0
...

user output
1
1
0
0
0
...
Truncated

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
100000
0 100000
0 99999
1 100000
0 99998
...

correct output
33
32
32
32
31
...

user output
33
32
32
32
31
...
Truncated

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
3
99999 99999
99999 100000
100000 100000

correct output
0
1
1

user output
0
1
1

Test 20

Group: 2, 3

Verdict: ACCEPTED

input
1
0 100000

correct output
33

user output
33

Test 21

Group: 3

Verdict:

input
100000
0 1000000000000000000
0 1000000000000000000
0 1000000000000000000
0 1000000000000000000
...

correct output
262145
262145
262145
262145
262145
...

user output
(empty)

Test 22

Group: 3

Verdict:

input
100000
179926689319432205 25677963778...

correct output
0
0
0
0
0
...

user output
(empty)

Test 23

Group: 3

Verdict:

input
100000
100110100011010101 11100011010...

correct output
74822
54944
140968
252594
23521
...

user output
(empty)

Test 24

Group: 3

Verdict:

input
100000
100110100011010102 11100011010...

correct output
74822
252594
94086
10836
11352
...

user output
(empty)

Test 25

Group: 3

Verdict: ACCEPTED

input
100000
256779637786129463 25677963778...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...
Truncated

Test 26

Group: 3

Verdict:

input
100000
0 1000000000000000000
0 999999999999999999
1 1000000000000000000
0 999999999999999998
...

correct output
262145
262144
262144
262144
262143
...

user output
(empty)

Test 27

Group: 3

Verdict: ACCEPTED

input
3
999999999999999999 99999999999...

correct output
0
1
1

user output
0
1
1

Test 28

Group: 3

Verdict: ACCEPTED

input
1
0 1000000000000000000

correct output
262145

user output
262145