Submission #418002

#	Time	Username	Problem	Language	Result	Execution time	Memory
418002		KULIKOLD	Sequence (BOI14_sequence)	C++17	100 / 100	331 ms	182208 KiB

sequence

//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
const ll DIM = 1E5+7;
const ll DIV = 7;
const ll MAXN = 11;
const ll SZ = 1<<10;
const ll INF = 1E18;
ll A[DIM],dp[DIM][DIV][MAXN],dp1[DIM][DIV][MAXN],suf[DIM][DIV][MAXN],po[DIV];
ll F(ll num,ll digit){
    while(num){
        if (num%10==digit)
            return 0;
        num/=10;
    }
    return 1<<digit;
}
void anchor(){
    ll h;
    ++h;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    po[0] = 1;
    for(ll i = 1;i<DIV;++i)
        po[i] = po[i-1]*10;
    ll n;
    cin>>n;
    for(ll i = 1;i<=n;++i){
        cin>>A[i];
    }
    for(ll i = 1;i<=n;++i){
        ll cur = 1<<A[i];
        for(ll div = 0;div<DIV;++div){
            for(ll num = 1;num<=10;++num){
                ll mask = 0;
                ll mask1 = 0;
                if (num>1 && i-po[div]>=1){
                    mask|=dp[i-po[div]][div][num-1]|F(po[div]*(num-1),A[i-po[div]]);
                    mask1|=dp1[i-po[div]][div][num-1]|F(po[div]*(num-1),A[i-po[div]]);
                }
                ll tmp = (SZ-1)^(1<<(num-1));
                ll tmp1 = tmp;
                if (num==1)
                    tmp = SZ-1;

                if (div>0){
                    if (num>1)
                        mask|=dp1[i][div-1][10]&tmp;
                    else mask|=dp[i][div-1][10]&tmp;
                    mask1|=dp1[i][div-1][10]&tmp1;
                }
                dp[i][div][num] = mask;
                dp1[i][div][num] = mask1;
            }

        }
    }
    for(ll i = n;i>=1;--i){
        ll cur = 1<<A[i];
        for(ll div = 0;div<DIV;++div){
            for(ll num = 0;num<=9;++num){
                ll mask = 0;
                if (num<9 && i+po[div]<=n){
                    mask|=suf[i+po[div]][div][num+1]|F(po[div]*(num+1),A[i+po[div]]);
                }
                ll tmp = (SZ-1)^(1<<num);
                if (div>0){
                    mask|=suf[i][div-1][0]&tmp;
                }
                suf[i][div][num] = mask;
            }
        }
    }
    ll ans = 0;
    for(ll r = 1;r<=1000;++r) {
        ll flag = 0;
        for (ll i = 1; i <= n; ++i) {
            if (F(r + i - 1, A[i]))
                flag = 1;
        }
        if (!flag){
            ans = r;
            break;
        }
    }
    ll res = INF;
    for(ll i = 1;i<=n;++i){
        for(ll div = 0;div<DIV;++div) {
            for (ll num = 1; num <= 9; ++num) {
                if (num * po[div] < i || po[div]*(10-num)-1+i<n)
                    continue;
                ll mask = F(po[div] * num, A[i]) | suf[i][div][num];
                if (num==1) {
                    mask |= dp1[i][div][num];
                    if(dp[i][div][num]!=dp1[i][div][num] && mask==0)
                        mask = 2;

                } else {
                    mask |= dp[i][div][num];
                }
                ll r = 0;
                if (mask == 1) {
                    r = 10;
                } else {
                    for (ll bit = 1; bit <= 9; ++bit) {
                        if (mask & (1 << bit)) {
                            r = r * 10 + bit;
                            if (mask & 1) {
                                r = r * 10;
                                mask ^= 1;
                            }
                        }
                    }
                }
                r = r * 10 + num;
                r*=po[div];
                r-=i-1;

                res = min(res,r);

            }
        }
    }

    cout<<res<<endl;
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:38:12: warning: unused variable 'cur' [-Wunused-variable]
   38 |         ll cur = 1<<A[i];
      |            ^~~
sequence.cpp:65:12: warning: unused variable 'cur' [-Wunused-variable]
   65 |         ll cur = 1<<A[i];
      |            ^~~
sequence.cpp:80:8: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   80 |     ll ans = 0;
      |        ^~~
sequence.cpp: In function 'void anchor()':
sequence.cpp:23:5: warning: 'h' is used uninitialized in this function [-Wuninitialized]
   23 |     ++h;
      |     ^~~

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33