Submission #338740

#	Time	Username	Problem	Language	Result	Execution time	Memory
338740		limabeans	Sequence (BOI14_sequence)	C++17	100 / 100	163 ms	1516 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll inf = 8e18;




ll solve(vector<int> a, bool flag9=true) {
    int n = a.size();
    if (n==1) {
	ll res = 0;
	for (int x=1; x<=9; x++) {
	    if (a[0]>>x&1) {
		res=res*10 + x;
		if (res==x && (a[0]&1)) {
		    // x is first digit, and we need 0
		    res=res*10;
		}
	    }
	}
	if (res==0 && (a[0]&1)) {
	    res = 10; //only 0
	}
	return res;
    } else {

	ll lo = inf;
	// iterate over last digit
	for (int x=0; x<9+flag9; x++) {
	    int d = x;
	    int mask = 0;
	    vector<int> na;
	    bool zero = false;
	    for (int i=0; i<n; i++) {
		mask |= (a[i] & (1023 ^ (1<<d)));
		if (d==0 && (a[i]&1)) {
		    zero = true;
		}
		d = (d+1) % 10;
		if (d==0 || i==n-1) {
		    na.push_back(mask);
		    mask = 0;
		}
	    }

	    ll cur = solve(na, !(n==2 && x==9))*10 + x;
	    if (cur==0 && zero) cur = 10;
	    lo = min(lo, cur);
	}

	return lo;
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	int d;
	cin>>d;
	a[i] = (1<<d);
	
    }
    cout<<solve(a)<<endl;    
    return 0;
}

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