QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#745148 | #8769. Champernowne Substring | cyj888 | WA | 91ms | 3860kb | C++14 | 4.4kb | 2024-11-14 07:25:56 | 2024-11-14 07:25:57 |
Judging History
answer
#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ott(i, l, r) for (__int128 i = (l); i <= (r); i ++)
#define tto(i, l, r) for (__int128 i = (r); i >= (l); i --)
using namespace std;
typedef long long ll;
typedef long double ld;
int read () {
int x = 0; bool f = false; char c = getchar ();
while (!isdigit (c)) f |= (c == '-'), c = getchar ();
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return f ? -x : x;
}
const int N = 1e6 + 110, mod = 998244353;
int T, n, m, k; __int128 res;
string str, sum;
vector <int> a, val;
inline string get (__int128 x) {
string ret = "";
while (x) ret += x % 10 + '0', x /= 10;
reverse (ret.begin (), ret.end ());
return ret;
}
inline __int128 cnt (__int128 x) {
__int128 ret = 0, now = 1; int c = 0;
while (now <= x / 10) ret += 9 * now * (++ c), now *= 10;
ret += (x - now + 1) * (++ c);
return ret;
}
inline void upd (const __int128 &v) {
return void (res = (!res || res > v) ? v : res);
}
void sol () {
cin >> str, n = str.size ();
sum = ""; ott (i, 1, 99999) sum += get (i);
//我tm想X人了:)
m = sum.size (); ott (i, 0, m - n) {//暴力去除位数<=5的
bool ok = true;
ott (j, 0, n - 1) if (str[j] ^ '?' && str[j] ^ sum[i + j]) {
ok = false; break;
}
if (ok) upd (i + 1);
}
__int128 now = 10; ott (l, 2, 26) {//存在边界
now *= 10; __int128 pre = cnt (now - 11);
sum = ""; ott (i, now - 10, now + 10) sum += get (i);
m = sum.size (); ott (i, 0, m - n) {
bool ok = true;
ott (j, 0, n - 1)
if (str[j] ^ '?' && str[j] ^ sum[i + j]) {
ok = false; break;
}
if (ok) upd (pre + i + 1);//, printf ("l = %d, i = %d\n", (int)l, (int)i);
}
}
//不存在边界,即位数均为l>=5的情况
ott (l, 5, 26) {//不进位
ott (v, 1, 9) {
ott (i, 1, l - 1) a.pb (-i);
a.pb (v);
}
m = a.size (); ott (i, 0, m - n) {
bool ok = true; val.resize (l + 1, -1);
ott (j, 0, n - 1) {
if (!(str[j] ^ '?')) continue;
if (a[i + j] < 0) {
if (!~val[-a[i + j]]) val[-a[i + j]] = str[j];
else if (val[-a[i + j]] ^ str[j]) ok = false;
}
else if (a[i + j] + '0' ^ str[j]) ok = false;
}
if (!(val[1] ^ '0')) ok = false;
if (ok) {
ott (j, 1, l - 1) if (!~val[j]) val[j] = '0' + (j == 1);
val[l] = '1', now = 0;
ott (j, 1, l) now = 10 * now + val[j] - '0';
upd (cnt (now - 1) + i + 1);
}
val.clear ();
}
a.clear ();
}
ott (l, 5, 26) {//有且仅有一个数进位,因为这些数最多5,6个
ott (c, 1, l - 1) {//枚举一次进了多少位/末9的连续个数
ott (v, 5, 9) {
ott (i, 1, l - c - 1) a.pb (-i);
a.pb (-(l - c + 1));
ott (i, 1, c - 1) a.pb (9);
a.pb (v);
}
ott (v, 0, 5) {
ott (i, 1, l - c) a.pb (-i);
ott (i, 1, c - 1) a.pb (0);
a.pb (v);
}
m = a.size (); ott (i, 0, m - n) {
bool ok = true; val.resize (l + 1, -1);
ott (j, 0, n - 1) {
if (!(str[j] ^ '?')) continue;
if (a[i + j] < 0) {
if (!~val[-a[i + j]]) val[-a[i + j]] = str[j];
else if (val[-a[i + j]] ^ str[j]) ok = false;
}
else if (a[i + j] + '0' ^ str[j]) ok = false;
}
// if (ok) cout << (int)l << " " << (int)c << " " << ok << endl;//, getchar ();
if (!~val[l - c] && !~val[l - c + 1]) {
val[l - c] = '1' + (l - c == 1),
val[l - c + 1] = '0' + (l - c == 1);
}
else if (~val[l - c] && ~val[l - c + 1]) {
if (val[l - c] ^ val[l - c + 1] + 1) {
ok = false;
}
}
else if (~val[l - c]) {
if (val[l - c] ^ '0') val[l - c + 1] = val[l - c] - 1;
else ok = false;
}
else {
if (val[l - c + 1] ^ '9') val[l - c] = val[l - c + 1] + 1;
else ok = false;
}
if (!(val[1] ^ '0')) ok = false;
if (ok) {
ott (j, 1, l - c - 1) if (!~val[j]) val[j] = '0' + (j == 1);
ott (j, l - c + 1, l) val[j] = '0'; now = 0;
ott (j, 1, l) now = 10 * now + val[j] - '0';
// if (now < 0) {
// cout << (int)(l - c) << endl;
// ott (j, 1, l) cout << (char)val[j]; cout << endl;getchar ();
// }
upd (cnt (now - 1) - 5 * l + i + 1);
}
val.clear ();
}
a.clear ();
}
}
cout << (int)(res % mod) << endl, res = 0;
return ;
}
int main () {
ios :: sync_with_stdio (false);
cin.tie (0), cout.tie (0);
cin >> T; while (T --) sol ();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 91ms
memory: 3860kb
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: 89ms
memory: 3752kb
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 788888870 488873 902034054 830780534 68888820 5882870
result:
wrong answer 5th lines differ - expected: '902934046', found: '788888870'