| Task: | Lukuvälit |
| Sender: | eliaskosunen |
| Submission time: | 2019-10-02 00:53:14 +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.04 s | 2, 3 | details |
| #15 | ACCEPTED | 0.05 s | 2, 3 | details |
| #16 | ACCEPTED | 0.05 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.20 s | 3 | details |
| #26 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #27 | ACCEPTED | 0.11 s | 3 | details |
| #28 | ACCEPTED | 0.12 s | 3 | details |
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,
1000000000,
1000000001,
1000000010,
1000000011,
1000000100,
1000000101,
1000000110,
1000000111,
1000001000,
1000001001,
1000001010,
1000001011,
1000001100,
1000001101,
1000001110,
1000001111,
1000010000,
1000010001,
1000010010,
1000010011,
1000010100,
1000010101,
1000010110,
1000010111,
1000011000,
1000011001,
1000011010,
1000011011,
1000011100,
1000011101,
1000011110,
1000011111,
1000100000,
1000100001,
1000100010,
1000100011,
1000100100,
1000100101,
1000100110,
1000100111,
1000101000,
1000101001,
1000101010,
1000101011,
1000101100,
1000101101,
1000101110,
1000101111,
1000110000,
1000110001,
1000110010,
1000110011,
1000110100,
1000110101,
1000110110,
1000110111,
1000111000,
1000111001,
1000111010,
1000111011,
1000111100,
1000111101,
1000111110,
1000111111,
1001000000,
1001000001,
1001000010,
1001000011,
1001000100,
1001000101,
1001000110,
1001000111,
1001001000,
1001001001,
1001001010,
1001001011,
1001001100,
1001001101,
1001001110,
1001001111,
1001010000,
1001010001,
1001010010,
1001010011,
1001010100,
1001010101,
1001010110,
1001010111,
1001011000,
1001011001,
1001011010,
1001011011,
1001011100,
1001011101,
1001011110,
1001011111,
1001100000,
1001100001,
1001100010,
1001100011,
1001100100,
1001100101,
1001100110,
1001100111,
1001101000,
1001101001,
1001101010,
1001101011,
1001101100,
1001101101,
1001101110,
1001101111,
1001110000,
1001110001,
1001110010,
1001110011,
1001110100,
1001110101,
1001110110,
1001110111,
1001111000,
1001111001,
1001111010,
1001111011,
1001111100,
1001111101,
1001111110,
1001111111,
1010000000,
1010000001,
1010000010,
1010000011,
1010000100,
1010000101,
1010000110,
1010000111,
1010001000,
1010001001,
1010001010,
1010001011,
1010001100,
1010001101,
1010001110,
1010001111,
1010010000,
1010010001,
1010010010,
1010010011,
1010010100,
1010010101,
1010010110,
1010010111,
1010011000,
1010011001,
1010011010,
1010011011,
1010011100,
1010011101,
1010011110,
1010011111,
1010100000,
1010100001,
1010100010,
1010100011,
1010100100,
1010100101,
1010100110,
1010100111,
1010101000,
1010101001,
1010101010,
1010101011,
1010101100,
1010101101,
1010101110,
1010101111,
1010110000,
1010110001,
1010110010,
1010110011,
1010110100,
1010110101,
1010110110,
1010110111,
1010111000,
1010111001,
1010111010,
1010111011,
1010111100,
1010111101,
1010111110,
1010111111,
1011000000,
1011000001,
1011000010,
1011000011,
1011000100,
1011000101,
1011000110,
1011000111,
1011001000,
1011001001,
1011001010,
1011001011,
1011001100,
1011001101,
1011001110,
1011001111,
1011010000,
1011010001,
1011010010,
1011010011,
1011010100,
1011010101,
1011010110,
1011010111,
1011011000,
1011011001,
1011011010,
1011011011,
1011011100,
1011011101,
1011011110,
1011011111,
1011100000,
1011100001,
1011100010,
1011100011,
1011100100,
1011100101,
1011100110,
1011100111,
1011101000,
1011101001,
1011101010,
1011101011,
1011101100,
1011101101,
1011101110,
1011101111,
1011110000,
1011110001,
1011110010,
1011110011,
1011110100,
1011110101,
1011110110,
1011110111,
1011111000,
1011111001,
1011111010,
1011111011,
1011111100,
1011111101,
1011111110,
1011111111,
1100000000,
1100000001,
1100000010,
1100000011,
1100000100,
1100000101,
1100000110,
1100000111,
1100001000,
1100001001,
1100001010,
1100001011,
1100001100,
1100001101,
1100001110,
1100001111,
1100010000,
1100010001,
1100010010,
1100010011,
1100010100,
1100010101,
1100010110,
1100010111,
1100011000,
1100011001,
1100011010,
1100011011,
1100011100,
1100011101,
1100011110,
1100011111,
1100100000,
1100100001,
1100100010,
1100100011,
1100100100,
1100100101,
1100100110,
1100100111,
1100101000,
1100101001,
1100101010,
1100101011,
1100101100,
1100101101,
1100101110,
1100101111,
1100110000,
1100110001,
1100110010,
1100110011,
1100110100,
1100110101,
1100110110,
1100110111,
1100111000,
1100111001,
1100111010,
1100111011,
1100111100,
1100111101,
1100111110,
1100111111,
1101000000,
1101000001,
1101000010,
1101000011,
1101000100,
1101000101,
1101000110,
1101000111,
1101001000,
1101001001,
1101001010,
1101001011,
1101001100,
1101001101,
1101001110,
1101001111,
1101010000,
1101010001,
1101010010,
1101010011,
1101010100,
1101010101,
1101010110,
1101010111,
1101011000,
1101011001,
1101011010,
1101011011,
1101011100,
1101011101,
1101011110,
1101011111,
1101100000,
1101100001,
1101100010,
1101100011,
1101100100,
1101100101,
1101100110,
1101100111,
1101101000,
1101101001,
1101101010,
1101101011,
1101101100,
1101101101,
1101101110,
1101101111,
1101110000,
1101110001,
1101110010,
1101110011,
1101110100,
1101110101,
1101110110,
1101110111,
1101111000,
1101111001,
1101111010,
1101111011,
1101111100,
1101111101,
1101111110,
1101111111,
1110000000,
1110000001,
1110000010,
1110000011,
1110000100,
1110000101,
1110000110,
1110000111,
1110001000,
1110001001,
1110001010,
1110001011,
1110001100,
1110001101,
1110001110,
1110001111,
1110010000,
1110010001,
1110010010,
1110010011,
1110010100,
1110010101,
1110010110,
1110010111,
1110011000,
1110011001,
1110011010,
1110011011,
1110011100,
1110011101,
1110011110,
1110011111,
1110100000,
1110100001,
1110100010,
1110100011,
1110100100,
1110100101,
1110100110,
1110100111,
1110101000,
1110101001,
1110101010,
1110101011,
1110101100,
1110101101,
1110101110,
1110101111,
1110110000,
1110110001,
1110110010,
1110110011,
1110110100,
1110110101,
1110110110,
1110110111,
1110111000,
1110111001,
1110111010,
1110111011,
1110111100,
1110111101,
1110111110,
1110111111,
1111000000,
1111000001,
1111000010,
1111000011,
1111000100,
1111000101,
1111000110,
1111000111,
1111001000,
1111001001,
1111001010,
1111001011,
1111001100,
1111001101,
1111001110,
1111001111,
1111010000,
1111010001,
1111010010,
1111010011,
1111010100,
1111010101,
1111010110,
1111010111,
1111011000,
1111011001,
1111011010,
1111011011,
1111011100,
1111011101,
1111011110,
1111011111,
1111100000,
1111100001,
1111100010,
1111100011,
1111100100,
1111100101,
1111100110,
1111100111,
1111101000,
1111101001,
1111101010,
1111101011,
1111101100,
1111101101,
1111101110,
1111101111,
1111110000,
1111110001,
1111110010,
1111110011,
1111110100,
1111110101,
1111110110,
1111110111,
1111111000,
1111111001,
1111111010,
1111111011,
1111111100,
1111111101,
1111111110,
1111111111,
10000000000,
10000000001,
10000000010,
10000000011,
10000000100,
10000000101,
10000000110,
10000000111,
10000001000,
10000001001,
10000001010,
10000001011,
10000001100,
10000001101,
10000001110,
10000001111,
10000010000,
10000010001,
10000010010,
10000010011,
10000010100,
10000010101,
10000010110,
10000010111,
10000011000,
10000011001,
10000011010,
10000011011,
10000011100,
10000011101,
10000011110,
10000011111,
10000100000,
10000100001,
10000100010,
10000100011,
10000100100,
10000100101,
10000100110,
10000100111,
10000101000,
10000101001,
10000101010,
10000101011,
10000101100,
10000101101,
10000101110,
10000101111,
10000110000,
10000110001,
10000110010,
10000110011,
10000110100,
10000110101,
10000110110,
10000110111,
10000111000,
10000111001,
10000111010,
10000111011,
10000111100,
10000111101,
10000111110,
10000111111,
10001000000,
10001000001,
10001000010,
10001000011,
10001000100,
10001000101,
10001000110,
10001000111,
10001001000,
10001001001,
10001001010,
10001001011,
10001001100,
10001001101,
10001001110,
10001001111,
10001010000,
10001010001,
10001010010,
10001010011,
10001010100,
10001010101,
10001010110,
10001010111,
10001011000,
10001011001,
10001011010,
10001011011,
10001011100,
10001011101,
10001011110,
10001011111,
10001100000,
10001100001,
10001100010,
10001100011,
10001100100,
10001100101,
10001100110,
10001100111,
10001101000,
10001101001,
10001101010,
10001101011,
10001101100,
10001101101,
10001101110,
10001101111,
10001110000,
10001110001,
10001110010,
10001110011,
10001110100,
10001110101,
10001110110,
10001110111,
10001111000,
10001111001,
10001111010,
10001111011,
10001111100,
10001111101,
10001111110,
10001111111,
10010000000,
10010000001,
10010000010,
10010000011,
10010000100,
10010000101,
10010000110,
10010000111,
10010001000,
10010001001,
10010001010,
10010001011,
10010001100,
10010001101,
10010001110,
10010001111,
10010010000,
10010010001,
10010010010,
10010010011,
10010010100,
10010010101,
10010010110,
10010010111,
10010011000,
10010011001,
10010011010,
10010011011,
10010011100,
10010011101,
10010011110,
10010011111,
10010100000,
10010100001,
10010100010,
10010100011,
10010100100,
10010100101,
10010100110,
10010100111,
10010101000,
10010101001,
10010101010,
10010101011,
10010101100,
10010101101,
10010101110,
10010101111,
10010110000,
10010110001,
10010110010,
10010110011,
10010110100,
10010110101,
10010110110,
10010110111,
10010111000,
10010111001,
10010111010,
10010111011,
10010111100,
10010111101,
10010111110,
10010111111,
10011000000,
10011000001,
10011000010,
10011000011,
10011000100,
10011000101,
10011000110,
10011000111,
10011001000,
10011001001,
10011001010,
10011001011,
10011001100,
10011001101,
10011001110,
10011001111,
10011010000,
10011010001,
10011010010,
10011010011,
10011010100,
10011010101,
10011010110,
10011010111,
10011011000,
10011011001,
10011011010,
10011011011,
10011011100,
10011011101,
10011011110,
10011011111,
10011100000,
10011100001,
10011100010,
10011100011,
10011100100,
10011100101,
10011100110,
10011100111,
10011101000,
10011101001,
10011101010,
10011101011,
10011101100,
10011101101,
10011101110,
10011101111,
10011110000,
10011110001,
10011110010,
10011110011,
10011110100,
10011110101,
10011110110,
10011110111,
10011111000,
10011111001,
10011111010,
10011111011,
10011111100,
10011111101,
10011111110,
10011111111,
10100000000,
10100000001,
10100000010,
10100000011,
10100000100,
10100000101,
10100000110,
10100000111,
10100001000,
10100001001,
10100001010,
10100001011,
10100001100,
10100001101,
10100001110,
10100001111,
10100010000,
10100010001,
10100010010,
10100010011,
10100010100,
10100010101,
10100010110,
10100010111,
10100011000,
10100011001,
10100011010,
10100011011,
10100011100,
10100011101,
10100011110,
10100011111,
10100100000,
10100100001,
10100100010,
10100100011,
10100100100,
10100100101,
10100100110,
10100100111,
10100101000,
10100101001,
10100101010,
10100101011,
10100101100,
10100101101,
10100101110,
10100101111,
10100110000,
10100110001,
10100110010,
10100110011,
10100110100,
10100110101,
10100110110,
10100110111,
10100111000,
10100111001,
10100111010,
10100111011,
10100111100,
10100111101,
10100111110,
10100111111,
10101000000,
10101000001,
10101000010,
10101000011,
10101000100,
10101000101,
10101000110,
10101000111,
10101001000,
10101001001,
10101001010,
10101001011,
10101001100,
10101001101,
10101001110,
10101001111,
10101010000,
10101010001,
10101010010,
10101010011,
10101010100,
10101010101,
10101010110,
10101010111,
10101011000,
10101011001,
10101011010,
10101011011,
10101011100,
10101011101,
10101011110,
10101011111,
10101100000,
10101100001,
10101100010,
10101100011,
10101100100,
10101100101,
10101100110,
10101100111,
10101101000,
10101101001,
10101101010,
10101101011,
10101101100,
10101101101,
10101101110,
10101101111,
10101110000,
10101110001,
10101110010,
10101110011,
10101110100,
10101110101,
10101110110,
10101110111,
10101111000,
10101111001,
10101111010,
10101111011,
10101111100,
10101111101,
10101111110,
10101111111,
10110000000,
10110000001,
10110000010,
10110000011,
10110000100,
10110000101,
10110000110,
10110000111,
10110001000,
10110001001,
10110001010,
10110001011,
10110001100,
10110001101,
10110001110,
10110001111,
10110010000,
10110010001,
10110010010,
10110010011,
10110010100,
10110010101,
10110010110,
10110010111,
10110011000,
10110011001,
10110011010,
10110011011,
10110011100,
10110011101,
10110011110,
10110011111,
10110100000,
10110100001,
10110100010,
10110100011,
10110100100,
10110100101,
10110100110,
10110100111,
10110101000,
10110101001,
10110101010,
10110101011,
10110101100,
10110101101,
10110101110,
10110101111,
10110110000,
10110110001,
10110110010,
10110110011,
10110110100,
10110110101,
10110110110,
10110110111,
10110111000,
10110111001,
10110111010,
10110111011,
10110111100,
10110111101,
10110111110,
10110111111,
10111000000,
10111000001,
10111000010,
10111000011,
10111000100,
10111000101,
10111000110,
10111000111,
10111001000,
10111001001,
10111001010,
10111001011,
10111001100,
10111001101,
10111001110,
10111001111,
10111010000,
10111010001,
10111010010,
10111010011,
10111010100,
10111010101,
10111010110,
10111010111,
10111011000,
10111011001,
10111011010,
10111011011,
10111011100,
10111011101,
10111011110,
10111011111,
10111100000,
10111100001,
10111100010,
10111100011,
10111100100,
10111100101,
10111100110,
10111100111,
10111101000,
10111101001,
10111101010,
10111101011,
10111101100,
10111101101,
10111101110,
10111101111,
10111110000,
10111110001,
10111110010,
10111110011,
10111110100,
10111110101,
10111110110,
10111110111,
10111111000,
10111111001,
10111111010,
10111111011,
10111111100,
10111111101,
10111111110,
10111111111,
11000000000,
11000000001,
11000000010,
11000000011,
11000000100,
11000000101,
11000000110,
11000000111,
11000001000,
11000001001,
11000001010,
11000001011,
11000001100,
11000001101,
11000001110,
11000001111,
11000010000,
11000010001,
11000010010,
11000010011,
11000010100,
11000010101,
11000010110,
11000010111,
11000011000,
11000011001,
11000011010,
11000011011,
11000011100,
11000011101,
11000011110,
11000011111,
11000100000,
11000100001,
11000100010,
11000100011,
11000100100,
11000100101,
11000100110,
11000100111,
11000101000,
11000101001,
11000101010,
11000101011,
11000101100,
11000101101,
11000101110,
11000101111,
11000110000,
11000110001,
11000110010,
11000110011,
11000110100,
11000110101,
11000110110,
11000110111,
11000111000,
11000111001,
11000111010,
11000111011,
11000111100,
11000111101,
11000111110,
11000111111,
11001000000,
11001000001,
11001000010,
11001000011,
11001000100,
11001000101,
11001000110,
11001000111,
11001001000,
11001001001,
11001001010,
11001001011,
11001001100,
11001001101,
11001001110,
11001001111,
11001010000,
11001010001,
11001010010,
11001010011,
11001010100,
11001010101,
11001010110,
11001010111,
11001011000,
11001011001,
11001011010,
11001011011,
11001011100,
11001011101,
11001011110,
11001011111,
11001100000,
11001100001,
11001100010,
11001100011,
11001100100,
11001100101,
11001100110,
11001100111,
11001101000,
11001101001,
11001101010,
11001101011,
11001101100,
11001101101,
11001101110,
11001101111,
11001110000,
11001110001,
11001110010,
11001110011,
11001110100,
11001110101,
11001110110,
11001110111,
11001111000,
11001111001,
11001111010,
11001111011,
11001111100,
11001111101,
11001111110,
11001111111,
11010000000,
11010000001,
11010000010,
11010000011,
11010000100,
11010000101,
11010000110,
11010000111,
11010001000,
11010001001,
11010001010,
11010001011,
11010001100,
11010001101,
11010001110,
11010001111,
11010010000,
11010010001,
11010010010,
11010010011,
11010010100,
11010010101,
11010010110,
11010010111,
11010011000,
11010011001,
11010011010,
11010011011,
11010011100,
11010011101,
11010011110,
11010011111,
11010100000,
11010100001,
11010100010,
11010100011,
11010100100,
11010100101,
11010100110,
11010100111,
11010101000,
11010101001,
11010101010,
11010101011,
11010101100,
11010101101,
11010101110,
11010101111,
11010110000,
11010110001,
11010110010,
11010110011,
11010110100,
11010110101,
11010110110,
11010110111,
11010111000,
11010111001,
11010111010,
11010111011,
11010111100,
11010111101,
11010111110,
11010111111,
11011000000,
11011000001,
11011000010,
11011000011,
11011000100,
11011000101,
11011000110,
11011000111,
11011001000,
11011001001,
11011001010,
11011001011,
11011001100,
11011001101,
11011001110,
11011001111,
11011010000,
11011010001,
11011010010,
11011010011,
11011010100,
11011010101,
11011010110,
11011010111,
11011011000,
11011011001,
11011011010,
11011011011,
11011011100,
11011011101,
11011011110,
11011011111,
11011100000,
11011100001,
11011100010,
11011100011,
11011100100,
11011100101,
11011100110,
11011100111,
11011101000,
11011101001,
11011101010,
11011101011,
11011101100,
11011101101,
11011101110,
11011101111,
11011110000,
11011110001,
11011110010,
11011110011,
11011110100,
11011110101,
11011110110,
11011110111,
11011111000,
11011111001,
11011111010,
11011111011,
11011111100,
11011111101,
11011111110,
11011111111,
11100000000,
11100000001,
11100000010,
11100000011,
11100000100,
11100000101,
11100000110,
11100000111,
11100001000,
11100001001,
11100001010,
11100001011,
11100001100,
11100001101,
11100001110,
11100001111,
11100010000,
11100010001,
11100010010,
11100010011,
11100010100,
11100010101,
11100010110,
11100010111,
11100011000,
11100011001,
11100011010,
11100011011,
11100011100,
11100011101,
11100011110,
11100011111,
11100100000,
11100100001,
11100100010,
11100100011,
11100100100,
11100100101,
11100100110,
11100100111,
11100101000,
11100101001,
11100101010,
11100101011,
11100101100,
11100101101,
11100101110,
11100101111,
11100110000,
11100110001,
11100110010,
11100110011,
11100110100,
11100110101,
11100110110,
11100110111,
11100111000,
11100111001,
11100111010,
11100111011,
11100111100,
11100111101,
11100111110,
11100111111,
11101000000,
11101000001,
11101000010,
11101000011,
11101000100,
11101000101,
11101000110,
11101000111,
11101001000,
11101001001,
11101001010,
11101001011,
11101001100,
11101001101,
11101001110,
11101001111,
11101010000,
11101010001,
11101010010,
11101010011,
11101010100,
11101010101,
11101010110,
11101010111,
11101011000,
11101011001,
11101011010,
11101011011,
11101011100,
11101011101,
11101011110,
11101011111,
11101100000,
11101100001,
11101100010,
11101100011,
11101100100,
11101100101,
11101100110,
11101100111,
11101101000,
11101101001,
11101101010,
11101101011,
11101101100,
11101101101,
11101101110,
11101101111,
11101110000,
11101110001,
11101110010,
11101110011,
11101110100,
11101110101,
11101110110,
11101110111,
11101111000,
11101111001,
11101111010,
11101111011,
11101111100,
11101111101,
11101111110,
11101111111,
11110000000,
11110000001,
11110000010,
11110000011,
11110000100,
11110000101,
11110000110,
11110000111,
11110001000,
11110001001,
11110001010,
11110001011,
11110001100,
11110001101,
11110001110,
11110001111,
11110010000,
11110010001,
11110010010,
11110010011,
11110010100,
11110010101,
11110010110,
11110010111,
11110011000,
11110011001,
11110011010,
11110011011,
11110011100,
11110011101,
11110011110,
11110011111,
11110100000,
11110100001,
11110100010,
11110100011,
11110100100,
11110100101,
11110100110,
11110100111,
11110101000,
11110101001,
11110101010,
11110101011,
11110101100,
11110101101,
11110101110,
11110101111,
11110110000,
11110110001,
11110110010,
11110110011,
11110110100,
11110110101,
11110110110,
11110110111,
11110111000,
11110111001,
11110111010,
11110111011,
11110111100,
11110111101,
11110111110,
11110111111,
11111000000,
11111000001,
11111000010,
11111000011,
11111000100,
11111000101,
11111000110,
11111000111,
11111001000,
11111001001,
11111001010,
11111001011,
11111001100,
11111001101,
11111001110,
11111001111,
11111010000,
11111010001,
11111010010,
11111010011,
11111010100,
11111010101,
11111010110,
11111010111,
11111011000,
11111011001,
11111011010,
11111011011,
11111011100,
11111011101,
11111011110,
11111011111,
11111100000,
11111100001,
11111100010,
11111100011,
11111100100,
11111100101,
11111100110,
11111100111,
11111101000,
11111101001,
11111101010,
11111101011,
11111101100,
11111101101,
11111101110,
11111101111,
11111110000,
11111110001,
11111110010,
11111110011,
11111110100,
11111110101,
11111110110,
11111110111,
11111111000,
11111111001,
11111111010,
11111111011,
11111111100,
11111111101,
11111111110,
11111111111,
100000000000,
100000000001,
100000000010,
100000000011,
100000000100,
100000000101,
100000000110,
100000000111,
100000001000,
100000001001,
100000001010,
100000001011,
100000001100,
100000001101,
100000001110,
100000001111,
100000010000,
100000010001,
100000010010,
100000010011,
100000010100,
100000010101,
100000010110,
100000010111,
100000011000,
100000011001,
100000011010,
100000011011,
100000011100,
100000011101,
100000011110,
100000011111,
100000100000,
100000100001,
100000100010,
100000100011,
100000100100,
100000100101,
100000100110,
100000100111,
100000101000,
100000101001,
100000101010,
100000101011,
100000101100,
100000101101,
100000101110,
100000101111,
100000110000,
100000110001,
100000110010,
100000110011,
100000110100,
100000110101,
100000110110,
100000110111,
100000111000,
100000111001,
100000111010,
100000111011,
100000111100,
100000111101,
100000111110,
100000111111,
100001000000,
100001000001,
100001000010,
100001000011,
100001000100,
100001000101,
100001000110,
100001000111,
100001001000,
100001001001,
100001001010,
100001001011,
100001001100,
100001001101,
100001001110,
100001001111,
100001010000,
100001010001,
100001010010,
100001010011,
100001010100,
100001010101,
100001010110,
100001010111,
100001011000,
100001011001,
100001011010,
100001011011,
100001011100,
100001011101,
100001011110,
100001011111,
100001100000,
100001100001,
100001100010,
100001100011,
100001100100,
100001100101,
100001100110,
100001100111,
100001101000,
100001101001,
100001101010,
100001101011,
100001101100,
100001101101,
100001101110,
100001101111,
100001110000,
100001110001,
100001110010,
100001110011,
100001110100,
100001110101,
100001110110,
100001110111,
100001111000,
100001111001,
100001111010,
100001111011,
100001111100,
100001111101,
100001111110,
100001111111,
100010000000,
100010000001,
100010000010,
100010000011,
100010000100,
100010000101,
100010000110,
100010000111,
100010001000,
100010001001,
100010001010,
100010001011,
100010001100,
100010001101,
100010001110,
100010001111,
100010010000,
100010010001,
100010010010,
100010010011,
100010010100,
100010010101,
100010010110,
100010010111,
100010011000,
100010011001,
100010011010,
100010011011,
100010011100,
100010011101,
100010011110,
100010011111,
100010100000,
100010100001,
100010100010,
100010100011,
100010100100,
100010100101,
100010100110,
100010100111,
100010101000,
100010101001,
100010101010,
100010101011,
100010101100,
100010101101,
100010101110,
100010101111,
100010110000,
100010110001,
100010110010,
100010110011,
100010110100,
100010110101,
100010110110,
100010110111,
100010111000,
100010111001,
100010111010,
100010111011,
100010111100,
100010111101,
100010111110,
100010111111,
100011000000,
100011000001,
100011000010,
100011000011,
100011000100,
100011000101,
100011000110,
100011000111,
100011001000,
100011001001,
100011001010,
100011001011,
100011001100,
100011001101,
100011001110,
100011001111,
100011010000,
100011010001,
100011010010,
100011010011,
100011010100,
100011010101,
100011010110,
100011010111,
100011011000,
100011011001,
100011011010,
100011011011,
100011011100,
100011011101,
100011011110,
100011011111,
100011100000,
100011100001,
100011100010,
100011100011,
100011100100,
100011100101,
100011100110,
100011100111,
100011101000,
100011101001,
100011101010,
100011101011,
100011101100,
100011101101,
100011101110,
100011101111,
100011110000,
100011110001,
100011110010,
100011110011,
100011110100,
100011110101,
100011110110,
100011110111,
100011111000,
100011111001,
100011111010,
100011111011,
100011111100,
100011111101,
100011111110,
100011111111,
100100000000,
100100000001,
100100000010,
100100000011,
100100000100,
100100000101,
100100000110,
100100000111,
100100001000,
100100001001,
100100001010,
100100001011,
100100001100,
100100001101,
100100001110,
100100001111,
100100010000,
100100010001,
100100010010,
100100010011,
100100010100,
100100010101,
100100010110,
100100010111,
100100011000,
100100011001,
100100011010,
100100011011,
100100011100,
100100011101,
100100011110,
100100011111,
100100100000,
100100100001,
100100100010,
100100100011,
100100100100,
100100100101,
100100100110,
100100100111,
100100101000,
100100101001,
100100101010,
100100101011,
100100101100,
100100101101,
100100101110,
100100101111,
100100110000,
100100110001,
100100110010,
100100110011,
100100110100,
100100110101,
100100110110,
100100110111,
100100111000,
100100111001,
100100111010,
100100111011,
100100111100,
100100111101,
100100111110,
100100111111,
100101000000,
100101000001,
100101000010,
100101000011,
100101000100,
100101000101,
100101000110,
100101000111,
100101001000,
100101001001,
100101001010,
100101001011,
100101001100,
100101001101,
100101001110,
100101001111,
100101010000,
100101010001,
100101010010,
100101010011,
100101010100,
100101010101,
100101010110,
100101010111,
100101011000,
100101011001,
100101011010,
100101011011,
100101011100,
100101011101,
100101011110,
100101011111,
100101100000,
100101100001,
100101100010,
100101100011,
100101100100,
100101100101,
100101100110,
100101100111,
100101101000,
100101101001,
100101101010,
100101101011,
100101101100,
100101101101,
100101101110,
100101101111,
100101110000,
100101110001,
100101110010,
100101110011,
100101110100,
100101110101,
100101110110,
100101110111,
100101111000,
100101111001,
100101111010,
100101111011,
100101111100,
100101111101,
100101111110,
100101111111,
100110000000,
100110000001,
100110000010,
100110000011,
100110000100,
100110000101,
100110000110,
100110000111,
100110001000,
100110001001,
100110001010,
100110001011,
100110001100,
100110001101,
100110001110,
100110001111,
100110010000,
100110010001,
100110010010,
100110010011,
100110010100,
100110010101,
100110010110,
100110010111,
100110011000,
100110011001,
100110011010,
100110011011,
100110011100,
100110011101,
100110011110,
100110011111,
100110100000,
100110100001,
100110100010,
100110100011,
100110100100,
100110100101,
100110100110,
100110100111,
100110101000,
100110101001,
100110101010,
100110101011,
100110101100,
100110101101,
100110101110};
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 < 64ull - __builtin_clzll(value); ++k) {
auto mask = 1 << k;
auto masked = value & mask;
val += (masked >> k) * power_of_10(k);
}
return val;
}
};
static constexpr auto n_precalc = sizeof(precalc) / sizeof(*precalc);
static constexpr auto max_precalc = precalc[n_precalc - 1];
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 >= max_precalc) {
pretend_binary bin{2478}; // 100110101110
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 |