Task: | Lukuvälit |
Sender: | eliaskosunen |
Submission time: | 2019-10-02 00:40:23 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 36 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 24 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#13 | ACCEPTED | 0.05 s | 2, 3 | details |
#14 | ACCEPTED | 0.03 s | 2, 3 | details |
#15 | ACCEPTED | 0.05 s | 2, 3 | details |
#16 | ACCEPTED | 0.04 s | 2, 3 | details |
#17 | ACCEPTED | 0.03 s | 2, 3 | details |
#18 | ACCEPTED | 0.05 s | 2, 3 | details |
#19 | ACCEPTED | 0.01 s | 2, 3 | details |
#20 | ACCEPTED | 0.01 s | 2, 3 | details |
#21 | TIME LIMIT EXCEEDED | -- | 3 | details |
#22 | TIME LIMIT EXCEEDED | -- | 3 | details |
#23 | TIME LIMIT EXCEEDED | -- | 3 | details |
#24 | TIME LIMIT EXCEEDED | -- | 3 | details |
#25 | ACCEPTED | 0.21 s | 3 | details |
#26 | TIME LIMIT EXCEEDED | -- | 3 | details |
#27 | ACCEPTED | 0.11 s | 3 | details |
#28 | ACCEPTED | 0.11 s | 3 | details |
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 decimalu64 value{0};// if value == 3, returns 11 in base 10,// which looks like 0b11i64 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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
100000 179926689319432205 25677963778... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100110100011010101 11100011010... |
correct output |
---|
74822 54944 140968 252594 23521 ... |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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 |