| Task: | Kyselyt |
| Sender: | eliaskosunen |
| Submission time: | 2017-10-06 22:01:48 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | 37 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 12 |
| #2 | ACCEPTED | 25 |
| #3 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.04 s | 1 | details |
| #2 | ACCEPTED | 0.05 s | 2 | details |
| #3 | TIME LIMIT EXCEEDED | -- | 3 | details |
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 ... |
| correct output |
|---|
| 0 1 7 7 6 ... |
| user output |
|---|
| 0 1 7 7 6 ... Truncated |
Test 2
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 1000 615664 916441 627600 279508 ... |
| correct output |
|---|
| 1 2 3 2 2 ... |
| user output |
|---|
| 1 2 3 2 2 ... Truncated |
Test 3
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 672274832941907421 260504693279721732 646999966092970935 100853063389774434 ... |
| correct output |
|---|
| 7 2 2 0 9 ... |
| user output |
|---|
| (empty) |