Submission #1157091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157091		the_coding_pooh	Sequence (BOI14_sequence)	C++20	100 / 100	818 ms	1356 KiB

sequence

#include <bits/stdc++.h>
#define uwu return 0;
 
using namespace std;
 
long long solve(vector <int> input, int cnt, int use_zero){
    if(cnt == 18)
        return 1;
    if(input.empty())
        return use_zero;
    if(input.size() == 1){
        if(!input[0])
            return use_zero;
        long long ret = 0;
        if(input[0] & 1){
            if(__builtin_popcount(input[0]) >= 2){
                input[0] ^= 1;
                int lb = input[0] & -input[0];
                ret = 10 * __lg(lb);
                input[0] ^= (1 << __lg(lb));
            }
            else
                return 10;
        }
        for (int k = 0; k < 10; k++){
            if(input[0] & (1 << k)){
                ret *= 10;
                ret += k;
            }
        }
        return ret;
    }
    long long ret = 1e18;
    for (int i = 0; i <= 9; i++){
        int nw = i;
        vector <int> bit_to_one;
        int now = 0;
        for(auto j:input){
            for (int k = 0; k < 10; k++){
                if(k != nw && (j & (1 << k))){
                    now |= (1 << k);
                }
            }
            nw++;
            if(nw == 10){
                nw = 0;
                bit_to_one.push_back(now);
                now = 0;
            }
        }
        if(now){
            bit_to_one.push_back(now);
            now = 0;
        }
        if((input[0] & 1) && (i == 0))
            use_zero = 1;
        if(i != 0)
            use_zero = 0;
        ret = min(ret, solve(bit_to_one, cnt + 1, use_zero) * 10 + i);
    }
    return ret;
}
 
int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N;
    cin >> N;
    vector <int> input;
    for (int i = 1, a; i <= N; i++){
        cin >> a;
        input.push_back((1 << a));
    }
    cout << solve(input, 0, 0) << '\n';
}

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