Kyselyt

#include <algorithm>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

template <typename T>
int count_digits(T number)
{
    int digits = 0;
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

template <typename T>
char get_digit(T number, std::size_t digit)
{
    std::ostringstream oss;
    oss << number;
    return oss.str()[digit];
}

template <typename T>
std::size_t get_next_pow10(T number)
{
    std::size_t i = 1;
    while ((i * 10) < number) {
        i *= 10;
    }
    return i;
}

struct series_point {
    std::size_t member{1};
    std::size_t number{1};

    constexpr series_point() = default;

    series_point& get_point(std::size_t m)
    {
        while (true) {
            if (member >= m) {
                return *this;
            }
            auto next_pow10 = get_next_pow10(number);
            auto dist_till_pow10 = [&]() -> std::size_t {
                if (next_pow10 <= number)
                    return 0;
                return next_pow10 - number;
            }();
            if (member - m >= 25 && dist_till_pow10 > 10) {
                auto digits = count_digits(number);
                member += dist_till_pow10 * digits;
                number += dist_till_pow10;
            }
            else {
                member += count_digits(number++);
            }
        }
    }

    series_point& get_prev()
    {
        member -= count_digits(--number);
        return *this;
    }

    char get_char(std::size_t m)
    {
        get_point(m);
        if (member > m) {
            get_prev();
        }
        return get_digit(number, m - member);
    }

    series_point copy() const
    {
        return *this;
    }

    friend std::ostream& operator<<(std::ostream& os, const series_point& p)
    {
        os << "member: " << p.member << ", number: " << p.number;
        return os;
    }
};

struct input {
    std::size_t i{0};
    std::size_t k{0};
    char result{0};

    friend std::ostream& operator<<(std::ostream& os, const input& i)
    {
        os << "i: " << i.i << ", k: " << i.k << ", result: " << i.result;
        return os;
    }
};

int main()
{
    /* series_point s; */
    /* assert(series_point{}.get_char(1) == '1'); */
    /* assert(series_point{}.get_char(10) == '1'); */
    /* assert(series_point{}.get_char(11) == '0'); */
    /* for (std::size_t i = 1; i <= 1010; ++i) { */
    /*     auto a = s.get_char(i); */
    /*     auto c = series_point{}.get_char(i); */
    /*     if (i % 29 == 0) { */
    /*         auto tmp = series_point{}; */
    /*         auto b = tmp.get_char(i); */
    /*         if (a != b) { */
    /*             std::cout << " * At i = " << i << ", a != b:\n" */
    /*                       << "   a = " << a << ", b = " << b << '\n' */
    /*                       << "   State of s (a):   " << s << '\n' */
    /*                       << "   State of tmp (b): " << tmp << '\n'; */
    /*         } */
    /*         if(b != c) { */
    /*             std::cout << " * At i = " << i << ", b != c:\n" */
    /*                       << "   b = " << b << ", c = " << c << '\n' */
    /*                       << "   State of tmp (b):   " << tmp << '\n'; */
    /*         } */
    /*     } */
    /* } */

    series_point s;
    int q;
    std::cin >> q;

    std::vector<input> inputs(q);
    {
        std::size_t ix = 0;
        for (auto& i : inputs) {
            i.i = ix;
            std::cin >> i.k;
            ++ix;
        }
        std::sort(inputs.begin(), inputs.end(),
                  [](input a, input b) { return a.k < b.k; });
    }

    for (auto& i : inputs) {
        i.result = s.get_char(i.k);
    }

    std::sort(inputs.begin(), inputs.end(),
              [](input a, input b) { return a.i < b.i; });
    for (auto& i : inputs) {
        std::cout << i.result << '\n';
    }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED