— Dark mode

Datatähti 2018 alku

Kyselyt

  • Start: 2017-10-02 00:00:00
  • End: 2017-10-16 00:00:00
  • Contest has ended
CSES - Datatähti 2018 alku - Results
Submission details
Task:Kyselyt
Sender:eliaskosunen
Submission time:2017-10-06 22:01:48 +0300
Language:C++
Status:READY
Result:37
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED25
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.05 s2details
#3--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:308:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     std::scanf("%d", &q);
                         ^
input/code.cpp:315:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             std::scanf("%zd", &i.k);
                                    ^

Code

#include <algorithm>
#include <cassert>
/* #include <iostream> */
#include <array>
#include <cstdio>
#include <string>
#include <vector>
 
template <typename T>
int count_digits(T number)
{
    int digits = 0;
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}
 
template <>
int count_digits<std::size_t>(std::size_t x)
{
    // clang-format off
    return (x < 10u ? 1 :   
        (x < 100u ? 2 :   
        (x < 1000u ? 3 :   
        (x < 10000u ? 4 :   
        (x < 100000u ? 5 :   
        (x < 1000000u ? 6 :   
        (x < 10000000u ? 7 :  
        (x < 100000000u ? 8 :  
        (x < 1000000000u ? 9 :
        (x < 10000000000u ? 10 :
        (x < 100000000000u ? 11 :
        (x < 1000000000000u ? 12 :
        (x < 10000000000000u ? 13 :
        (x < 100000000000000u ? 14 :
        (x < 1000000000000000u ? 15 :
        (x < 10000000000000000u ? 16 :
        (x < 100000000000000000u ? 17 :
        (x < 1000000000000000000u ? 18 :
        (x < 10000000000000000000u ? 19 :
        20)))))))))))))))))));
    // clang-format on
}
 
template <typename T>
std::size_t pow10(T pow)
{
    T n = 1;
    for (T i = 1; i <= pow; ++i) {
        n *= 10;
    }
    return n;
}
 
template <>
std::size_t pow10<std::size_t>(std::size_t pow)
{
    static std::array<std::size_t, 20> p = {{1u,
                                             10u,
                                             100u,
                                             1000u,
                                             10000u,
                                             100000u,
                                             1000000u,
                                             10000000u,
                                             100000000u,
                                             1000000000u,
                                             10000000000u,
                                             100000000000u,
                                             1000000000000u,
                                             10000000000000u,
                                             100000000000000u,
                                             1000000000000000u,
                                             10000000000000000u,
                                             100000000000000000u,
                                             1000000000000000000u,
                                             10000000000000000000u}};
    return p[pow];
}
 
template <typename T>
char get_digit(T number, std::size_t digit)
{
    digit = count_digits(number) - digit - 1;
    return (number / pow10(digit)) % 10 + '0';
}
 
template <typename T>
T get_next_pow10(T number)
{
    T i = 1;
    while ((i * 10) < number) {
        i *= 10;
    }
    return i;
}
 
/* template <> */
/* std::size_t get_next_pow10(std::size_t number) */
/* { */
/*     if (pow10(10) > number) { */
/*         if (pow10(15) > number) { */
/*             if (pow10(17) > number) { */
/*                 if (pow10(18) > number) { */
/*                     if (pow10(19) > number) { */
/*                         return pow10(19); */
/*                     } */
/*                     else { */
/*                         return pow10(18); */
/*                     } */
/*                 } */
/*                 else { */
/*                     return pow10(17); */
/*                 } */
/*             } */
/*             else { */
/*                 if (pow10(16) > number) { */
/*                     return pow10(16); */
/*                 } */
/*                 else { */
/*                     return pow10(15); */
/*                 } */
/*             } */
/*         } */
/*         else { */
/*             if (pow10(12) > number) { */
/*                 if (pow10(13) > number) { */
/*                     if (pow10(14) > number) { */
/*                         return pow10(14); */
/*                     } */
/*                     else { */
/*                         return pow10(13); */
/*                     } */
/*                 } */
/*                 else { */
/*                     return pow10(12); */
/*                 } */
/*             } */
/*             else { */
/*                 if (pow10(11) > number) { */
/*                     return pow10(11); */
/*                 } */
/*                 else { */
/*                     return pow10(10); */
/*                 } */
/*             } */
/*         } */
/*     } */
/*     else { */
/*         if (pow10(5) > number) { */
/*             if (pow10(7) > number) { */
/*                 if (pow10(8) > number) { */
/*                     if (pow10(9) > number) { */
/*                         return pow10(9); */
/*                     } */
/*                     else { */
/*                         return pow10(8); */
/*                     } */
/*                 } */
/*                 else { */
/*                     return pow10(7); */
/*                 } */
/*             } */
/*             else { */
/*                 if (pow10(16) > number) { */
/*                     return pow10(16); */
/*                 } */
/*                 else { */
/*                     return pow10(15); */
/*                 } */
/*             } */
/*         } */
/*         else { */
/*             if (pow10(2) > number) { */
/*                 if (pow10(3) > number) { */
/*                     if (pow10(4) > number) { */
/*                         return pow10(4); */
/*                     } */
/*                     else { */
/*                         return pow10(3); */
/*                     } */
/*                 } */
/*                 else { */
/*                     return pow10(2); */
/*                 } */
/*             } */
/*             else { */
/*                 if (pow10(1) > number) { */
/*                     return pow10(1); */
/*                 } */
/*                 else { */
/*                     return pow10(0); */
/*                 } */
/*             } */
/*         } */
/*     } */
/* } */
 
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;
            }
            if (member - m >= 25) {
                const auto digits = count_digits(number);
                const auto next_pow10 = get_next_pow10(number);
                const auto dist_till_pow10 = [&]() -> std::size_t {
                    if (next_pow10 <= number)
                        return 0;
                    return next_pow10 - number;
                }();
                if (dist_till_pow10 > 1 &&
                    dist_till_pow10 <
                        std::numeric_limits<std::size_t>::min() - 1000) {
                    member += dist_till_pow10 * digits;
                    number += dist_till_pow10;
                    continue;
                }
            }
            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(pow10(1) == 10); */
    /* assert(pow10(2) == 100); */
    /* std::cout << get_digit(13, 0) << ' ' << get_digit(13, 1) << '\n'; */
    /* assert(get_digit(1, 0) == '1'); */
    /* assert(get_digit(13, 1) == '3'); */
    /* 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::scanf("%d", &q);
 
    std::vector<input> inputs(q);
    {
        std::size_t ix = 0;
        for (auto& i : inputs) {
            i.i = ix;
            std::scanf("%zd", &i.k);
            /* 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'; */
        std::putchar(i.result);
        std::putchar('\n');
    }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1000
582
214
723
273
...
view save

correct output
0
1
7
7
6
...
view save

user output
0
1
7
7
6
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
615664
916441
627600
279508
...
view save

correct output
1
2
3
2
2
...
view save

user output
1
2
3
2
2
...
Truncated

Test 3

Group: 3

Verdict:

input
1000
672274832941907421
260504693279721732
646999966092970935
100853063389774434
...
view save

correct output
7
2
2
0
9
...
view save

user output
(empty)

Tasks

A Merkkijono-B Fraktaali-C Kyselyt-D Bittijono-E Eppapeli-

Submissions (eliaskosunen)

2017-10-07 14:20:19 1002017-10-07 14:17:54 882017-10-07 14:03:51 02017-10-07 13:41:53 02017-10-07 00:57:38 02017-10-07 00:37:31 122017-10-07 00:07:10 372017-10-06 23:50:00 372017-10-06 23:00:45 372017-10-06 22:20:44 372017-10-06 22:01:48 372017-10-06 21:23:32 372017-10-06 21:13:17 372017-10-06 21:03:48 02017-10-06 20:36:18 372017-10-06 20:33:38 372017-10-06 20:15:34 372017-10-06 19:57:37 252017-10-06 19:54:26 25