QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #428936 | #8769. Champernowne Substring | ucup-team180# | WA | 19ms | 3736kb | C++17 | 5.8kb | 2024-06-01 23:11:57 | 2024-06-01 23:11:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
vector<__int128_t> TEN;
string to_string(__int128_t A){
string ans;
while (A != 0){
ans += '0' + (int) (A % 10);
A /= 10;
}
reverse(ans.begin(), ans.end());
return ans;
}
__int128_t get(__int128_t A){
string S = to_string(A);
int N = S.size();
__int128_t ans = 0;
for (int i = 1; i < N; i++){
ans += (TEN[i] - TEN[i - 1]) * i;
}
ans += (A - TEN[N - 1]) * N;
return ans;
}
int main(){
TEN.resize(31);
TEN[0] = 1;
for (int i = 0; i < 30; i++){
TEN[i + 1] = TEN[i] * 10;
}
int t;
cin >> t;
string C;
for (int i = 1; i <= 1010; i++){
C += to_string(i);
}
int C_LEN = C.size();
__int128_t INF = TEN[30];
for (int i = 0; i < t; i++){
string s;
cin >> s;
int N = s.size();
__int128_t ans = INF;
for (int j = 0; j <= C_LEN - N; j++){
bool ok = true;
for (int k = 0; k < N; k++){
if (C[j + k] != s[k] && s[k] != '?'){
ok = false;
}
}
if (ok){
ans = min(ans, (__int128_t) j);
}
}
for (int j = 4; j <= N + 1; j++){
for (int k = 0; k < j; k++){
vector<int> idx = {-k};
while (idx.back() < N){
int a = idx.back() + j;
idx.push_back(a);
}
int cnt = idx.size() - 1;
vector<int> d(j, -1);
bool no_carry_ok = true;
for (int l = 0; l < cnt; l++){
for (int m = 0; m < j; m++){
int p = idx[l] + m;
if (0 <= p && p < N){
if (s[p] != '?'){
if (m != j - 1){
if (d[m] == -1){
d[m] = s[p] - '0';
} else if (d[m] != s[p] - '0'){
no_carry_ok = false;
}
} else {
if (d[m] == -1){
if (s[p] - '0' - l < 0 || s[p] - '0' - l > 10 - cnt){
no_carry_ok = false;
} else {
d[m] = s[p] - '0' - l;
}
} else if (d[m] != s[p] - '0' - l){
no_carry_ok = false;
}
}
}
}
}
}
if (d[0] == 0){
no_carry_ok = false;
}
if (no_carry_ok){
if (d[0] == -1){
d[0] = 1;
}
for (int l = 1; l < j; l++){
if (d[l] == -1){
d[l] = 0;
}
}
__int128_t A = 0;
for (int l = 0; l < j; l++){
A *= 10;
A += d[l];
}
ans = min(ans, get(A) + k);
}
for (int l = 1; l < cnt; l++){
for (int m = 0; m < j; m++){
bool ok = true;
vector<int> d(j, -1);
for (int n = j - m; n < j - 1; n++){
d[n] = 9;
}
d[j - 1] = 10 - l;
for (int n = 0; n < cnt; n++){
for (int o = 0; o < j; o++){
int p = idx[n] + o;
if (0 <= p && p < N){
if (s[p] != '?'){
if (o < j - m - 1){
if (d[o] == -1){
d[o] = s[p] - '0';
} else if (d[o] != s[p] - '0'){
ok = false;
}
} else if (o == j - m - 1){
if (d[o] == -1){
if (n < l){
if (s[p] - '0' == 9){
ok = false;
} else {
d[o] = s[p] - '0';
}
} else {
if (s[p] - '0' == 0){
ok = false;
} else {
d[o] = s[p] - '0' - 1;
}
}
} else if (n < l && d[o] != s[p] - '0' || n >= l && d[o] != s[p] - '0' - 1){
ok = false;
}
} else if (o < j - 1){
if (n < l && s[p] - '0' != 9){
ok = false;
}
if (n >= l && s[p] - '0' != 0){
ok = false;
}
} else {
if (s[p] - '0' != (10 - l + n) % 10){
ok = false;
}
}
}
}
}
}
if (d[0] == 0){
ok = false;
}
if (ok){
if (d[0] == -1){
d[0] = 1;
}
for (int n = 1; n < j; n++){
if (d[n] == -1){
d[n] = 0;
}
}
__int128_t A = 0;
for (int n = 0; n < j; n++){
A *= 10;
A += d[n];
}
ans = min(ans, get(A) + k);
}
}
}
for (int l = 1; k - j + (l - 1) * j < N; l++){
__int128_t A = TEN[j] - l;
__int128_t A2 = A;
string S;
S += to_string(A2).substr(k);
while (S.size() < N){
A2++;
S += to_string(A2);
}
bool ok = true;
for (int m = 0; m < N; m++){
if (S[m] != s[m] && s[m] != '?'){
ok = false;
}
}
if (ok){
ans = min(ans, get(A) + k);
}
}
}
}
ans++;
cout << (long long) (ans % MOD) << endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3736kb
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: 19ms
memory: 3736kb
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 38883 830780534 38883 38882
result:
wrong answer 7th lines differ - expected: '902034054', found: '38883'