QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #439902 | #8769. Champernowne Substring | ucup-team045 | WA | 14ms | 3924kb | C++20 | 9.3kb | 2024-06-12 20:25:08 | 2024-06-12 20:25:08 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;
const int mod = 998244353;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
const __int128_t INF = 1e30;
string t;
for(int i = 1; i < 100000; i++){
t += to_string(i);
}
auto check = [&](const string &t, const string &s){
for(int i = 0; i + s.size() - 1 < t.size(); i++){
bool ok = true;
for(int j = 0; j < s.size(); j++){
if (s[j] != '?' and s[j] != t[i + j]){
ok = false;
break;
}
}
if (ok){
return i;
}
}
return -1;
};
__int128_t pow10[30];
pow10[0] = 1;
for(int i = 1; i < 30; i++){
pow10[i] = pow10[i - 1] * 10;
}
auto i2s = [&](__int128_t x){
string ans;
while(x){
ans.push_back(x % 10 + '0');
x /= 10;
}
reverse(ans.begin(), ans.end());
return ans;
};
auto get = [&](__int128_t x){
__int128_t ans = 0;
for(int i = 1; ; i++){
if (x >= pow10[i]){
ans += i * (pow10[i] - pow10[i - 1]);
}
else{
ans += i * (x - pow10[i - 1] + 1);
break;
}
}
return ans;
};
int T;
cin >> T;
while(T--){
string s;
cin >> s;
const int n = s.size();
int res = check(t, s);
if (res != -1){
cout << res + 1 << '\n';
continue;
}
__int128_t ans = INF;
// 在不同数位交界,即段内的数字可能位数不同
for(int i = 5; i <= n + 1; i++){
string s1, s2;
__int128_t x = pow10[i - 1] - 1;
for(; s1.size() < n; x -= 1){
s1 = i2s(x) + s1;
}
__int128_t y = pow10[i - 1];
for(; s2.size() < n; y += 1){
s2 += i2s(y);
}
int pos = check(s1 + s2, s);
if (pos != -1){
ans = min(ans, get(x) + pos + 1);
}
}
auto update = [&](__int128_t val){
if (val > INF / 2) return;
auto bk = val;
string ss;
while(ss.size() < 2 * n){
ss += i2s(val);
val += 1;
}
int pos = check(ss, s);
if (pos != -1){
ans = min(ans, get(bk - 1) + pos + 1);
}
};
// 段内每个数字位数都相同,注意到十位及以上最多变化一次
// 每个数字位数为a
// 偏移为b
// 第一个数字个位为c
// 进位的时候最后有d个9(不包含个位)
auto solve = [&](int a, int b, int c){
if (a == 9 and b == 8 and c == 9){
int t = 0;
}
vector<string> v;
if (b != 0){
v.push_back(string(a - b, '?') + s.substr(0, b));
}
for(int i = b; i < n; i += a){
v.push_back(s.substr(i, a));
}
if (!v.empty() and v.back().size() < a){
v.back() += string(a - v.back().size(), '?');
}
int pos = v.size();
for(int i = 0; i < v.size(); i++){
if (i + c == 10) pos = i;
int t = (c + i) % 10;
if (v[i].back() != '?' and v[i].back() != char('0' + t)){
return;
}
}
vector<int> state(a);
for(int i = 0; i < a; i++){
for(auto &str : v){
if (str[i] != '?'){
state[i] |= 1 << (str[i] - '0');
}
}
}
if (pos == v.size()){
__int128_t val = 0;
for(int i = 0; i < a; i++){
if (__builtin_popcount(state[i]) >= 2) return;
if (i == 0){
if (state[i] == 0){
val = val * 10 + 1;
}
else{
int t = __lg(state[i]);
if (t == 0) return;
val = val * 10 + t;
}
}
else if (i == a - 1){
val = val * 10 + c;
}
else{
if (state[i] == 0){
val = val * 10 + 0;
}
else{
val = val * 10 + __lg(state[i]);
}
}
}
update(val);
return;
}
__int128_t mn = INF;
__int128_t cur = c;
for(int d = 0; d + 1 < a; d++){
bool ok = true;
if (d != 0){
for(int j = 0; j < pos; j++){
if (v[j][a - 1 - d] != '?' and v[j][a - 1 - d] != '9'){
ok = false;
break;
}
}
if (!ok) break;
for(int j = pos; j < v.size(); j++){
if (v[j][a - 1 - d] != '?' and v[j][a - 1 - d] != '0'){
ok = false;
break;
}
}
if (!ok) break;
cur += pow10[d] * 9;
}
int s1 = 0, s2 = 0;
for(int j = 0; j < pos; j++){
if (v[j][a - 1 - (d + 1)] != '?'){
s1 |= 1 << (v[j][a - 1 - (d + 1)] - '0');
}
}
for(int j = pos; j < v.size(); j++){
if (v[j][a - 1 - (d + 1)] != '?'){
s2 |= 1 << (v[j][a - 1 - (d + 1)] - '0');
}
}
int val = -1;
if (__builtin_popcount(s1) >= 2 or __builtin_popcount(s2) >= 2) continue;
if (s1 > 0 and s2 > 0){
int t1 = __lg(s1);
int t2 = __lg(s2);
if (t1 + 1 == t2){
val = t1;
}
}
else if (s1 > 0){
int t1 = __lg(s1);
if (d + 1 == a - 1){
if (t1 != 0 and t1 != 9){
val = t1;
}
}
else{
if (t1 != 9){
val = t1;
}
}
}
else if (s2 > 0){
int t2 = __lg(s2);
int t1 = t2 - 1;
if (d + 1 == a - 1){
if (t1 > 0){
val = t1;
}
}
else{
if (t1 >= 0){
val = t1;
}
}
}
else{
if (d + 1 == a - 1){
val = 1;
}
else{
val = 0;
}
}
if (val == -1) continue;
__int128_t t = cur + val * pow10[d + 1];
for(int j = 0; j + 1 < a - (d + 1); j++){
if (__builtin_popcount(state[j]) >= 2){
ok = false;
break;
}
if (j == 0){
if (state[j] == 0){
t = t + pow10[a - 1 - j];
}
else{
int k = __lg(state[j]);
if (k == 0){
ok = false;
break;
}
t = t + k * pow10[a - 1 - j];
}
}
else{
if (state[j] == 0){
}
else{
t = t + __lg(state[j]) * pow10[a - 1 - j];
}
}
}
if (ok){
mn = min(mn, t);
}
}
update(mn);
};
for(int i = 5; i <= n + 1; i++){
for(int j = 0; j < i; j++){
for(int k = 0; k < 10; k++){
solve(i, j, k);
}
}
}
cout << int(ans % mod) << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 3752kb
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: 14ms
memory: 3924kb
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: 13ms
memory: 3752kb
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:
108802929 797951281 758593545 842297792 660254768 34219412 452740345 132221552 692870314 277899385
result:
wrong answer 4th lines differ - expected: '919282423', found: '842297792'