QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#439824 | #8769. Champernowne Substring | HKOI0# | WA | 749ms | 3828kb | C++14 | 3.2kb | 2024-06-12 19:09:25 | 2024-06-12 19:09:25 |
Judging History
answer
#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define int __int128_t
using namespace std;
string to_string(int x){
if (x == 0) {
return "0";
} else if (x < 0) {
return "-" + to_string(x);
}
string res;
while (x) {
res.push_back('0' + x % 10);
x /= 10;
}
assert(res.size());
reverse(res.begin(), res.end());
return res;
}
ostream& operator<< (ostream& out, int x){
return out << to_string(x);
}
int f(int x){
--x;
int pw = 1, b = 1;
int res = 0;
while (x >= pw) {
int l = pw, r = min(x, pw * 10 - 1);
res += b * (r - l + 1);
pw *= 10; ++b;
}
return res + 1;
}
string g(int pos, int len){
--pos;
int pw = 1, b = 1;
while (pos >= pw * b * 9) {
pos -= pw * b * 9;
pw *= 10; ++b;
}
string t;
assert(pos / b + pw > 0);
int base = pos / b + pw, rem = pos % b;
while (t.size() < len + 50) {
t += to_string(base); ++base;
}
return t.substr(rem, len);
}
int to_int(string s){
int res = 0;
for (auto c : s) {
res = res * 10 + (c - '0');
}
return res;
}
bool matched(string s, string t){
if (s.size() != t.size()) return false;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?') continue;
if (s[i] != t[i]) return false;
}
return true;
}
int ans;
string s;
void test(int x){
if (x <= 0) return;
// cout << x << ' ' << g(x, s.size()) << endl;
if (matched(s, g(x, s.size()))) {
ans = min(ans, x);
}
}
bool can(string& s, int idx, char c){
if (s[idx] == '?') return true;
return s[idx] == c;
}
string superimpose(string& s, int l){
string r(l, '?');
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?') continue;
if (r[i % l] == '?') {
r[i % l] = s[i];
} else if (r[i % l] != s[i]) {
r[i % l] = 'X';
}
}
return r;
}
void solve() {
cin >> s;
ans = (__int128_t) 1 << 120;
for (int pw10 = 1; pw10 < 1e26; pw10 *= 10) {
int x = f(pw10);
for (int y = -50; y <= 50; y++) {
test(x + y);
}
}
for (int i = 1; i <= 10000; i++) {
test(i);
}
for (int l = 3; l <= 25; l++) {
for (int pad = 0; pad < l; pad++) {
string t = string(pad, '?') + s;
int rem = l - t.size() % l;
t += string(rem, '?');
assert(t.size() % l == 0);
assert(t.size() / l <= 10);
int n = t.size();
for (int i = 0; i < n / l; i++) {
for (int c = 0; c < l; c++) {
for (int x = 0; x <= 8; x++) {
string u; u.push_back('0' + x);
for (int i = 0; i < c; i++) {
u.push_back('9');
}
bool ok = true;
for (int j = l - u.size(); j < l; j++) {
ok &= can(t, i * l + j, u[j - (l - u.size())]);
}
if (!ok) continue;
string La = superimpose(t, l).substr(0, l - c - 1);
for (auto c : La) {
if (!c) ok = false;
}
if (!ok) continue;
int y = to_int(La);
y = y * 10 + x;
for (int j = 0; j < c; j++) {
y = y * 10 + 9;
}
test(f(y) - i * l + pad);
}
}
}
}
}
const int MOD = 998244353;
cout << ans % MOD << '\n';
}
int32_t main(){
#ifndef LOCAL
cin.tie(0)->sync_with_stdio(false);
#endif
int64_t t = 1;
cin >> t;
while (t--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 437ms
memory: 3828kb
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: 0
Accepted
time: 749ms
memory: 3620kb
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 830780534 68888820 5882870
result:
ok 10 lines
Test #3:
score: -100
Wrong Answer
time: 513ms
memory: 3612kb
input:
10 23573?0208935200503593500 08?9?1188980?661?18161467 22000103111010?24490??02? 4?129184?3644311331226625 9014217281609919609168?18 27809?1808?34646796569990 5116137658333853138917519 8778798398090800698?93888 742?9472125?9529272277272 5260238541343?22235629222
output:
500292333 500292333 500292333 500292333 194206422 500292333 452740345 92216689 500292333 363629923
result:
wrong answer 1st lines differ - expected: '108802929', found: '500292333'