QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#439808#8769. Champernowne Substringucup-team045WA 135ms18596kbC++208.2kb2024-06-12 18:32:072024-06-12 18:32:08

Judging History

你现在查看的是最新测评结果

  • [2024-06-12 18:32:08]
  • 评测
  • 测评结果:WA
  • 用时:135ms
  • 内存:18596kb
  • [2024-06-12 18:32:07]
  • 提交

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 < 2000000; 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(x);
            }
            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);
            }
        };

        update(1000001090083);

        // 段内每个数字位数都相同,注意到十位及以上最多变化一次
        // 每个数字位数为a
        // 偏移为b
        // 第一个数字个位为c
        // 进位的时候最后有d个9(不包含个位)
        auto solve = [&](int a, int b, int c){
            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 = 1; 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 + 1] * 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');
                    }
                }
                if (d + 1 == a - 1 and (s1 & 1)){
                    s1 ^= 1;
                }
                int val = -1;
                for(int j = 0; j + 1 < 10; j++){
                    if ((s1 >> j & 1) and (s2 >> j + 1 & 1)){
                        val = j;
                        break;
                    }
                }
                if (val == -1) continue;
                __int128_t t = cur + val * pow10[d + 2];
                for(int j = 0; j < 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';
    }

}

詳細信息

Test #1:

score: 100
Accepted
time: 51ms
memory: 18596kb

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: 135ms
memory: 18560kb

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
10545692
488873
68888876
830780534
5888885
5882870

result:

wrong answer 5th lines differ - expected: '902934046', found: '10545692'