제출 #584698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584698		MohammadAghil	수열 (BOI14_sequence)	C++17	100 / 100	175 ms	1420 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss secounf 
#define all(x) begin(x), end(x)
#define pb push_back

const ll mod = 1e9+7, maxn = 5e2+1, inf = ll(1e9)+5;

ll slv(vector<int> a, bool can = true){
     bool ok = false;
     for(int c: a) ok |= c > 0;
     if(!ok) return 0;
     if(sz(a) == 1){
          int x = a[0], res = 0, mn = 0;
          if(x&1){
               mn = 1;
               per(i,10,1) if(x>>i&1) mn = i;
               res = mn*10;
          }
          rep(i,mn+1,10) if(x>>i&1) res = res*10 + i;
          return res;
     }
     // cout << sz(a) << endl;
     ll ans = 10987654321000000ll;
     rep(d,0,10){
          if(d == 9 && !can) break;
          vector<int> b{0};
          bool has_zero = false;
          int cr = d;
          rep(i,0,sz(a)){
               if(a[i]>>cr&1) b.back() |= a[i]^(1<<cr);
               else b.back() |= a[i];
               if(!cr && (a[i]&1)) has_zero = true; 
               cr++;
               if(cr == 10) {
                    cr = 0;
                    if(i - sz(a) + 1) b.pb(0);
               }
          }
          // cout << sz(b) << '\n';
          ll res = slv(b, d != 9 || sz(a) > 2)*10 + d;
          if(!res && has_zero) res = 10;
          ans = min(ans, res);
     }
     return ans;
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int n; cin >> n;
     vector<int> a(n);
     rep(i,0,n){
          cin >> a[i], a[i] = 1<<a[i]; 
     }
     cout << slv(a) << '\n';
     return 0;
}

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