QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #637110 | #8769. Champernowne Substring | nhuang685 | WA | 612ms | 3640kb | C++23 | 10.3kb | 2024-10-13 09:42:57 | 2024-10-13 09:42:59 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-10-12 11:22:13
*
*
*/
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif
using i128 = __int128_t;
template <class T> constexpr T INF = T{};
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <> constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399
template <>
constexpr i128 INF<i128>
= i128{INF<int64_t>} << 64 | INF<int64_t>; // 84069761239290679208598432424319205183
constexpr int MOD = 998'244'353;
constexpr int MXLG = 25;
constexpr std::array<i128, MXLG + 1> p10 = []() {
std::array<i128, MXLG + 1> ans{};
ans[0] = 1;
for (int i = 1; i <= MXLG; ++i) {
ans[i] = ans[i - 1] * 10;
}
return ans;
}();
int log10(i128 val) {
for (int i = 0; i <= MXLG; ++i) {
if (val < p10[i]) {
return i - 1;
}
}
return MXLG;
}
i128 pos(i128 val) {
int lg = log10(val);
i128 ans = 0;
for (int i = lg; i >= 0; --i) {
ans += (i + 1) * (val - p10[i] + 1);
val = p10[i] - 1;
}
return ans;
}
std::string to_string(i128 val) {
if (val <= std::numeric_limits<uint64_t>::max()) {
return std::to_string(static_cast<uint64_t>(val));
}
std::string ans;
while (val > 0) {
ans += static_cast<char>('0' + val % 10);
val /= 10;
}
std::reverse(ans.begin(), ans.end());
return ans;
}
i128 stoi128(const std::string& s) {
i128 ans = 0;
for (char c : s) {
assert(c != '?');
ans = 10 * ans + (c - '0');
}
return ans;
}
bool match(const std::string& s, const std::string& ls) {
int n = static_cast<int>(s.size());
for (int i = 0; i < n; ++i) {
if (s[i] != '?' && ls[i] != '?' && s[i] != ls[i]) {
return false;
}
}
return true;
}
constexpr int MX = 100000;
void solve() {
std::string s;
std::cin >> s;
int n = static_cast<int>(s.size());
i128 ans = INF<i128>;
// starts from 1..10^5
for (i128 i = 1; i <= MX; ++i) {
int lg = log10(i);
for (int st = -lg; st <= 0; ++st) {
std::string ls;
for (i128 val = i; static_cast<int>(ls.size()) + st < n; ++val) {
ls += to_string(val);
}
if (match(s, ls.substr(-st))) {
ans = std::min(ans, pos(i - 1) + 1 - st);
}
}
}
// includes power of 10
for (int lg = 5; lg <= MXLG; ++lg) {
for (int p = -lg; p < n; ++p) {
int st = p;
i128 fi = p10[lg];
while (st > 0) {
st -= lg;
--fi;
}
std::string ls;
for (i128 val = fi; static_cast<int>(ls.size()) + st < n; ++val) {
ls += to_string(val);
}
if (match(s, ls.substr(-st))) {
ans = std::min(ans, pos(fi - 1) + 1 - st);
}
}
}
// one number
{
std::string ls = s;
for (int i = 1; i < static_cast<int>(ls.size()); ++i) {
if (ls[i] == '?') {
ls[i] = '0';
}
}
int off = 0;
if (ls[0] == '0') {
++off;
ls.insert(ls.begin(), '1');
} else if (ls[0] == '?') {
ls[0] = '1';
}
ans = std::min(ans, pos(stoi128(ls) - 1) + off + 1);
}
// no carry
for (int lg = 5; lg <= MXLG; ++lg) {
int wi = lg + 1;
int tp = (wi - n % wi) % wi;
int sz = n + tp;
for (int pl = 0; pl <= tp; ++pl) {
int pr = tp - pl;
std::string ss = std::string(pl, '?') + s + std::string(pr, '?');
std::string ls(wi, '?');
bool g = true;
for (int i = 0; i < sz; i += wi) {
for (int j = 0; j < wi; ++j) {
if (ss[i + j] == '?') {
continue;
}
if (j == wi - 1) {
int dv = ss[i + j] - '0';
if (dv < i / wi || ls[j] - '0' != dv - i / wi) {
g = false;
break;
}
ls[j] = static_cast<char>(dv - i / wi + '0');
} else {
int dv = ss[i + j] - '0';
if ((j == 0 && dv == 0) || ls[j] != ss[i + j]) {
g = false;
break;
}
ls[j] = ss[i + j];
}
}
}
if (g && ls[0] != '0') {
if (ls[0] == '?') {
ls[0] = '1';
}
for (int i = 1; i < wi; ++i) {
if (ls[i] == '?') {
ls[i] = '0';
}
}
ans = std::min(ans, pos(stoi128(ls) - 1) + pl + 1);
}
}
}
// carry
for (int lg = 5; lg <= MXLG; ++lg) {
int wi = lg + 1;
int tp = (wi - n % wi) % wi;
int sz = n + tp;
for (int pl = 0; pl <= tp; ++pl) {
int pr = tp - pl;
std::string ss = std::string(pl, '?') + s + std::string(pr, '?');
for (int cpos = wi; cpos < sz; cpos += wi) {
for (int cw = 1; cw < wi; ++cw) {
std::string ls(wi, '?');
ls[wi - 1] = static_cast<char>(10 - cpos / wi + '0');
for (int i = wi - cw; i < wi - 1; ++i) {
ls[i] = '9';
}
bool g = true;
for (int i = 0; i < cpos; i += wi) {
for (int j = 0; j < wi; ++j) {
if (ss[i + j] == '?') {
continue;
}
if (j == wi - 1) {
int dv = ss[i + j] - '0';
if (dv < i / wi || (ls[j] != '?' && ls[j] - '0' != dv - i / wi)) {
g = false;
break;
}
ls[j] = static_cast<char>(dv - i / wi + '0');
} else {
int dv = ss[i + j] - '0';
if (i >= wi - cw && dv != 9) {
g = false;
break;
}
if (i == wi - cw - 1 && dv == 9) {
g = false;
break;
}
if ((j == 0 && dv == 0) || (ls[j] != '?' && ls[j] != ss[i + j])) {
g = false;
break;
}
ls[j] = ss[i + j];
}
}
}
if (!g) {
continue;
}
for (int i = cpos; i < sz; i += wi) {
for (int j = 0; j < wi; ++j) {
if (ss[i + j] == '?') {
continue;
}
if (j == wi - 1) {
int dv = ss[i + j] - '0';
int od = dv - i / wi + 10;
if (ls[j] - '0' != od) {
g = false;
break;
}
ls[j] = static_cast<char>(od + '0');
} else {
int dv = ss[i + j] - '0';
if (j >= wi - cw) {
if (dv != 0) {
g = false;
break;
}
dv = 9;
} else if (j == wi - cw - 1) {
if (dv == 0) {
g = false;
break;
}
--dv;
}
if ((j == 0 && dv == 0) || (ls[j] != '?' && ls[j] != dv + '0')) {
g = false;
break;
}
ls[j] = static_cast<char>(dv + '0');
}
}
}
if (g && ls[0] != '0') {
if (ls[0] == '?') {
ls[0] = '1';
}
for (int i = 1; i < wi - cw; ++i) {
if (ls[i] == '?') {
ls[i] = '0';
}
}
ans = std::min(ans, pos(stoi128(ls) - 1) + pl + 1);
}
}
}
}
}
dbg(to_string(ans));
#ifdef LOCAL
i128 l = 1, r = static_cast<i128>(2e25);
while (l < r) {
i128 mid = l + (r - l) / 2;
if (pos(mid) + 1 >= ans) {
r = mid;
} else {
l = mid + 1;
}
}
dbg(to_string(l));
#endif
std::cout << static_cast<int>(ans % MOD) << '\n';
}
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int t;
std::cin >> t;
for (int i = 0; i < t; ++i) {
dbg(i + 1);
solve();
bar();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 281ms
memory: 3640kb
input:
9 0 ???1 121 1?1?1 ??5?54?50?5?505?65?5 000000000000 ?2222222 ?3????????9??8???????1??0 9?9??0????????????2
output:
11 7 14 10 314159 796889014 7777 8058869 38886
result:
ok 9 lines
Test #2:
score: -100
Wrong Answer
time: 612ms
memory: 3572kb
input:
10 0000000000000000000000000 0000000?002100000000000?0 6999?999?999999989?999999 0???0?1000?0??000?????0?1 9??9?999998?9?999999100?0 96?9997999?8999991????010 99?99??999999999??????99? ?0?0000?00000000?0210?0?0 99?999?999?99?9??999?9?9? 9?????9?99?99??9??99??9??
output:
545305036 237403177 73613435 583252822 902934046 488873 68888876 329890171 68888869 5882870
result:
wrong answer 2nd lines differ - expected: '574985081', found: '237403177'