Task: | Kyselyt |
Sender: | eliaskosunen |
Submission time: | 2017-10-06 23:50:00 +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.03 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:211: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:232: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 <cassert>/* #include <iostream> */#include <array>#include <cstdio>#include <map>#include <set>#include <string>#include <unordered_map>#include <vector>std::size_t count_digits(std::size_t x){// clang-format offreturn (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;}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 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};bool operator<(const input& i) const{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);/* 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; *//* } */for (auto i = 0; i < q; ++i) {input tmp{};std::scanf("%zd", &tmp.k);tmp.i = i;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'); *//* } */}
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) |