Submission #66171

#	Time	Username	Problem	Language	Result	Execution time	Memory
66171		Benq	Sequence (BOI14_sequence)	C++11	100 / 100	860 ms	15468 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const ll INF = 1e18;
const int MX = 100000;

const int MOD = (119 << 23) + 1, root = 3; // = 998244353
// For p < 2^30 there is also e.g. (5 << 25, 3), (7 << 26, 3),
// (479 << 21, 3) and (483 << 21, 5). The last two are > 10^9.

ll po (ll b, ll p) { return !p?1:po(b*b%MOD,p/2)*(p&1?b:1)%MOD; }
ll inv (ll b) { return po(b,MOD-2); }

int ad(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }
int sub(int a, int b) { return (a-b+MOD)%MOD; }
int mul(int a, int b) { return (ll)a*b%MOD; }

int AD(int& a, int b) { return a = ad(a,b); }
int SUB(int& a, int b) { return a = sub(a,b); }
int MUL(int& a, int b) { return a = mul(a,b); }

int L[1<<18], R[1<<18], tmp[1<<18];

namespace NTT {
    int get(int s) {
        return s > 1 ? 32 - __builtin_clz(s - 1) : 0;
    }
    
    int roots[1<<18];
    
	void ntt(int *a, bool f = 0) { // clearly not own
	    int N = 1<<18, P = MOD;
		int i, j, k, x, y, z;
		j = 0;
		for (i = 1; i < N; i++) {
			for (k = N >> 1; j >= k; k >>= 1) j -= k;
			j += k;
			if (i < j) {
				k = a[i];
				a[i] = a[j];
				a[j] = k;
			}
		}
		for (i = 1; i < N; i <<= 1) {
			x = po(3, P / i >> 1);
			for (j = 0; j < N; j += i << 1) {
				y = 1;
				for (k = 0; k < i; k++) {
					z = (long long)a[i | j | k] * y % P;
					a[i | j | k] = a[j | k] - z;
					if (a[i | j | k] < 0) a[i | j | k] += P;
					a[j | k] += z;
					if (a[j | k] >= P) a[j | k] -= P;
					y = (long long)y * x % P;
				}
			}
		}
	}
	/*
    void ntt(int* a) { 
        int n = 1<<18, x = 18;
        roots[0] = 1, roots[1] = po(root,(MOD-1)/n);
        FOR(i,2,n) roots[i] = mul(roots[i-1],roots[1]);
        
        array<int,1<<18> res, RES;
        F0R(i,1<<18) res[i] = a[i];
        
        FOR(i,1,x+1) {
            int inc = n>>i;
            F0R(j,inc) for (int k = 0; k < n; k += inc) {
                int t = 2*k+j; if (t >= n) t -= n;
                RES[k+j] = ad(res[t],mul(roots[k],res[t+inc]));
            }
            swap(res,RES);
        }
        
        F0R(i,1<<18) a[i] = res[i];
    }*/
    
    void ntt_rev(int* a) {
        ntt(a);
        int in = inv(1<<18);
        F0R(i,1<<18) MUL(a[i],in);
        reverse(a+1,a+(1<<18));
    }
    
    void conv() {
        ntt(L), ntt(R);
        F0R(i,1<<18) tmp[i] = mul(L[i],R[i]);
        ntt_rev(tmp);
        //F0R(i,1<<18) cout << tmp[i] << " ";
        //cout << "\n";
    }
}

ll ans = INF;
int res[10][MX], res2[10][MX], RES[MX], RES2[MX];
int K, B[MX], digYes[MX], digNo[MX];

int match(int x, int y) {
    while (x) {
        if (x % 10 == y) return 1;
        x /= 10;
    }
    return 0;
}

ll tri(int x, int y) {
    if (x == 0) return y;
    if (x == 1) x ^= 2;
    ll t = 0;
    FOR(i,1,10) if (x&(1<<i)) {
        t = i;
        x ^= 1<<i;
        break;
    }
    F0R(i,10) if (x&(1<<i)) {
        t = 10*t+i;
        x ^= 1<<i;
    }
    return t;
}

ll solve(pi a, pi b) { // what about leading zeroes??
    ll t = INF;
    F0R(i,9) {
        int A = min(a.f,a.f^(1<<i));
        int B = min(b.f,b.f^(1<<(i+1)));
        t = min(t,10*tri(A|B,(a.f&1) || (i == 0 && a.s))+i);
        
        A = min(A,A^(1<<9));
        B = min(B,B^(1<<0));
        t = min(t,100*tri(A|B,a.s)+10*i+9);
    }
    return MX*t;
}

pi get0(int st) {
    pi ret = {0,0};
    F0R(i,10) if (res[i][st] == 1) ret.f ^= 1<<i;
    if (RES[st] == 1) ret.s = 1;
    return ret;
}

pi get1(int st) {
    pi ret = {0,0};
    F0R(i,10) if (res2[i][st] == 1) ret.f ^= 1<<i;
    if (RES2[st] == 1) ret.s = 1;
    return ret;
}

ll test(int st) {
    pi a = get0(st), b = get1(st);
    // if (st == 0) cout << a.f << " " << a.s << "\n";
    ll ret = st+solve(a,b);
    return ret;
}

void gen() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    FOR(i,1,MX) digNo[i] = digNo[i/10]|(1<<(i%10));
    F0R(i,MX) {
        digYes[i] = digNo[i];
        if (i < MX/10) digYes[i] |= 1;
    }
    cin >> K;
    F0R(i,K) cin >> B[i];
}

void oops(int x) {
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    F0R(i,MX) L[i] = !(digYes[i]&(1<<x));
    F0R(i,K) R[MX-i] = (B[i] == x);
    NTT::conv();
    F0R(i,MX) if (tmp[i]) res2[x][i] = 1;
    F0R(i,MX) if (tmp[i+MX]) res[x][i] = 1;
}

void OOPS(int x = 0) {
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    F0R(i,MX) L[i] = !(digNo[i]&(1<<x));
    F0R(i,K) R[MX-i] = (B[i] == x);
    NTT::conv();
    F0R(i,MX) if (tmp[i]) RES2[i] = 1;
    F0R(i,MX) if (tmp[i+MX]) RES[i] = 1;
}

int main() {
    gen();
    F0R(i,10) oops(i);
    OOPS();
    F0R(i,MX) ans = min(ans,test(i));
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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