QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#427820 | #8769. Champernowne Substring | ucup-team004# | WA | 95ms | 3704kb | C++20 | 5.7kb | 2024-06-01 15:59:41 | 2024-06-01 15:59:42 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
std::string pref;
using i128 = __int128;
i128 find(i128 n) {
n--;
i128 ans = 0;
int len = 1;
for (i128 p = 1; p <= n; p *= 10, len++) {
ans += std::min(9 * p, n - p + 1) * len;
}
return ans;
}
std::string toString(i128 n) {
std::string s;
while (n) {
s += '0' + n % 10;
n /= 10;
}
std::reverse(s.begin(), s.end());
return s;
}
void solve() {
std::string s;
std::cin >> s;
for (int i = 0; i + s.size() <= pref.size(); i++) {
int ok = 1;
for (int j = 0; j < s.size(); j++) {
if (s[j] != '?' && pref[i + j] != s[j]) {
ok = 0;
break;
}
}
if (ok) {
std::cout << i + 1 << "\n";
return;
}
}
i128 ans = 0;
const int n = s.size();
// case 1: 1 number
for (int i = 0; i < n; i++) {
if (i == 0) {
if (s[i] == '0') {
ans = 10;
} else if (s[i] == '?') {
ans = 1;
} else {
ans = s[i] - '0';
}
} else if (s[i] == '?') {
ans = 10 * ans;
} else {
ans = 10 * ans + s[i] - '0';
}
}
ans = find(ans);
if (s[0] == '0') {
ans++;
}
auto checkv = [&](i128 v, int l) {
if (v < 10000) {
return;
}
i128 pos = find(v) - l;
const i128 v0 = v;
const int l0 = l;
int r = l;
i64 vl = v;
std::string t(n, '?');
while (l > 0) {
vl--;
std::string s = toString(vl);
for (int i = s.size() - 1; i >= 0; i--) {
if (l > 0) {
t[--l] = s[i];
}
}
}
while (r < n) {
std::string s = toString(v);
v++;
for (int i = 0; i < s.size(); i++) {
if (r < n) {
t[r++] = s[i];
}
}
}
for (int i = 0; i < n; i++) {
if (s[i] != '?' && s[i] != t[i]) {
return;
}
}
ans = std::min(ans, pos);
// std::cerr << "checkv " << toString(v0) << " " << l0 << "\n";
// std::cerr << t << "\n";
};
auto check = [&](const std::vector<int> &a, int l) {
for (int i = 0; i < a.size(); i++) {
if (a[i] < 0 || a[i] >= 10) {
return;
}
}
if (a[0] == 0) {
return;
}
i64 v = 0;
for (int i = 0; i < a.size(); i++) {
v = 10 * v + a[i];
}
checkv(v, l);
};
// case 2: 9...9 or 10...0
for (i128 p = 10000, len = 5; len <= 26; p *= 10, len++) {
for (int i = 0; i < n; i++) {
checkv(p - 1, i);
checkv(p, i);
}
}
// case 3: 2 numbers
for (int i = 1; i < n; i++) {
for (int len = std::max({5, n - i, i}); len <= n + 1; len++) {
for (int c = 0; c < len; c++) {
std::vector<int> a(len, -1);
for (int j = 0; j < i; j++) {
if (s[j] != '?') {
a[len - i + j] = s[j] - '0';
}
}
for (int j = i; j < n; j++) {
if (s[j] != '?') {
a[j - i] = s[j] - '0';
}
}
for (int j = 0; j < len; j++) {
if (a[j] == '?') {
a[j] = j == 0 ? 1 : 0;
}
}
for (int j = len - c; j < len; j++) {
a[j] = 0;
}
check(a, i);
a[len - 1 - c]++;
check(a, i);
}
}
}
// case 4: 3+ numbers
for (int i = 0; i < n; i++) {
for (int len = 5; len <= n - i; len++) {
for (int c = 0; c < len; c++) {
std::vector<int> a(len, -1);
for (int j = 0; j < n; j++) {
if (s[j] != '?') {
a[(j - i + len * 100) % len] = s[j] - '0';
}
}
for (int j = i; j < i + len; j++) {
if (s[j] != '?') {
a[j - i] = s[j] - '0';
}
}
for (int j = 0; j < len; j++) {
if (a[j] == '?') {
a[j] = j == 0 ? 1 : 0;
}
}
for (int j = len - c; j < len; j++) {
a[j] = 0;
}
for (int v = 0; v < 10; v++) {
a[len - 1 - c] = v;
check(a, i);
}
for (int j = len - c; j < len; j++) {
a[j] = 9;
}
for (int v = 0; v < 10; v++) {
a[len - 1 - c] = v;
check(a, i);
}
}
}
}
std::cout << int((ans + 1) % P) << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 1;
while (pref.size() < 100000) {
pref += std::to_string(n);
n++;
}
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 11ms
memory: 3652kb
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: 95ms
memory: 3704kb
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 574985081 788888865 5889591 902934046 488873 902034054 329890171 68888820 5882870
result:
wrong answer 8th lines differ - expected: '830780534', found: '329890171'