CSES - Datatähti 2018 alku - Results
Submission details
Task:Kyselyt
Sender:eliaskosunen
Submission time:2017-10-07 00:37:31 +0300
Language:C++
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#20.21 s2details
#3--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:233: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:285:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             std::scanf("%zd", &tmp.k);
                                      ^

Code

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdio>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
std::size_t count_digits(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
}
std::size_t pow10(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];
}
char get_digit(std::size_t number, std::size_t digit)
{
digit = count_digits(number) - digit - 1;
return (number / pow10(digit)) % 10 + '0';
}
std::size_t get_matching_pow10(std::size_t number)
{
return count_digits(number);
}
std::size_t get_next_pow10(std::size_t number)
{
return get_matching_pow10(number) + 1;
}
std::size_t get_amount_of_numbers_with_length(std::size_t len)
{
return 9 * pow10(len - 1);
}
std::size_t get_amount_of_members_with_length(std::size_t len)
{
return get_amount_of_numbers_with_length(len) * len;
}
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)
{
if (m < member) {
return get_preceding(m);
}
while (true) {
if (member >= m) {
return *this;
}
if (m - member >= 25) {
const auto digits = count_digits(number);
const auto amount = get_amount_of_numbers_with_length(digits);
if (amount > number + 1) {
const auto dist_till_pow10 = amount - number;
if (dist_till_pow10 > 2) {
member += dist_till_pow10 * digits;
number += dist_till_pow10;
continue;
}
}
/* const auto next_pow10 = get_next_pow10(number); */
/* if (next_pow10 > number) { */
/* const auto dist_till_pow10 = next_pow10 - number; */
/* if (dist_till_pow10 > 2) { */
/* member += dist_till_pow10 * digits; */
/* number += dist_till_pow10; */
/* continue; */
/* } */
/* } */
}
member += count_digits(number++);
}
}
series_point& get_prev()
{
member -= count_digits(--number);
return *this;
}
series_point& get_preceding(std::size_t m)
{
while (true) {
if (member <= m) {
return *this;
}
if (member - m >= 25) {
const auto digits = count_digits(number);
const auto current_pow10 = get_matching_pow10(number);
if (current_pow10 < number) {
const auto dist_till_pow10 = number - current_pow10;
if (dist_till_pow10 > 2) {
member -= dist_till_pow10 * digits;
number -= dist_till_pow10;
continue;
}
}
}
member -= count_digits(number--);
}
}
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};
std::size_t prev{0};
bool operator<(const input& i) const
{
/* if(prev > k + 1000) { */
/* return false; */
/* } */
return k < i.k;
}
/* 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);
#if 0
std::vector<input> inputs(q);
{
auto i = 0;
for (auto& input : inputs) {
input.i = i;
std::scanf("%zd", &input.k);
++i;
}
}
std::vector<std::size_t> outputs(q);
{
std::size_t prev = 0;
for (auto& input : inputs) {
if (input.k < prev && prev - input.k > 10000 &&
input.k < pow10(9)) {
s = series_point{};
}
outputs[input.i] = s.get_char(input.k);
prev = input.k;
}
}
for (auto& o : outputs) {
std::putchar(o);
std::putchar('\n');
}
#elif 1
/* std::vector<input> inputs(q); */
/* std::multiset<input> inputs{}; */
std::vector<input> inputs(q);
std::vector<std::size_t> input_keys(q);
/* std::unordered_map<std::size_t, input> inputs{}; */
/* std::vector<std::size_t> input_keys(q); */
{
/* std::size_t ix = 0; */
/* for (auto& i : inputs) { */
/* for (auto ix = 0; ix < q; ++ix) { */
/* input tmp{}; */
/* std::scanf("%zd", &tmp.k); */
/* tmp.i = ix; */
/* inputs.insert(std::move(tmp)); */
/* inputs.insert(std::make_pair(tmp.k, tmp)); */
/* input_keys[ix] = tmp.k; */
/* } */
std::size_t prev = 0;
for (auto i = 0; i < q; ++i) {
input tmp{};
std::scanf("%zd", &tmp.k);
tmp.i = i;
tmp.prev = prev;
prev = tmp.k;
inputs[i] = std::move(tmp);
}
std::sort(inputs.begin(), inputs.end());
for (auto i = 0; i < q; ++i) {
input_keys[i] = inputs[i].i;
}
}
/* std::vector<input> inputs(q); */
/* { */
/* std::size_t i = 0; */
/* for (auto& input : inputs) { */
/* std::scanf("%zd", &input.k); */
/* input.i = i; */
/* ++i; */
/* } */
/* } */
/* std::vector<std::size_t> outputs(q); */
/* for(auto i = 0; i < q; ++i) { */
/* outputs[i] = */
/* } */
std::vector<std::size_t> outputs(q);
for (auto i = 0; i < q; ++i) {
outputs[input_keys[i]] = s.get_char(inputs[i].k);
}
for (auto& o : outputs) {
std::putchar(o);
std::putchar('\n');
}
/* for (auto& i : outputs) { */
/* std::putchar(i); */
/* std::putchar('\n'); */
/* } */
#endif
}

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:

input
1000
615664
916441
627600
279508
...

correct output
1
2
3
2
2
...

user output
(empty)

Test 3

Group: 3

Verdict:

input
1000
672274832941907421
260504693279721732
646999966092970935
100853063389774434
...

correct output
7
2
2
0
9
...

user output
(empty)