Submission #843551

#	Time	Username	Problem	Language	Result	Execution time	Memory
843551		manizare	Sequence (BOI14_sequence)	C++14	100 / 100	320 ms	2640 KiB

sequence

#include <bits/stdc++.h> 
 
#define int long long 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int> 
#define int long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 1e5 + 10 , inf = 1e17 + 10  ;
int a10[18] ;

int dfs(vector <int> vec,  int ok){
  if(vec.size() == 0)return ok ;
  if(vec.size() == 1){
    if(vec[0] == 0){
      return ok ;
    }
    if(vec[0] == 1){
      return 10 ;
    }
    vector <int> vj ;
    for(int i = 0 ;i < 10 ; i++){
      if(vec[0]>>i&1){
        vj.pb(i) ; 
      }
    }
    if(vj[0] == 0){
      swap(vj[0], vj[1]);
    }
    int ans = 0;
    for(int i= 0  ; i < vj.size() ; i++){
      ans *= 10 ;
      ans += vj[i] ;
    }
    return ans ; 
  }
  int ans = inf ; 
  for(int i = 0 ; i < 10 ; i++){
    int t =0  , k = i ;
    vector <int> vec2 ;
    for(int j = 0;  j < vec.size() ; j++){
      if(k == 10){
        k =0 ; 
        vec2.pb(t) ;
        t = 0 ;
      }
      if(vec[j]>>k&1){
        vec[j] -= (1<<k) ;
        t |=  vec[j] ;
        vec[j]+= (1<<k) ;
      }else{
        t |= vec[j] ; 
      }
      k++;
    }
    vec2.pb(t) ;
    if(vec2 == vec && ok == (i==0)){
      continue ;
    }
    ans = min(ans ,  dfs(vec2 , (i==0) * (vec[0]%2)) * 10 + i )  ;
  }  
  return ans ; 
}

signed main(){
  ios::sync_with_stdio(false); cin.tie(0) ;  
  vector<int>vec ; 
  int n ;cin >> n ;
  for(int i = 1; i <= n; i++){
    int x;
    cin >> x ;
    vec.pb((1<<x)) ;
  } 
   cout << dfs(vec , 1) ;
}
/*
4 7 8 9 1 
4 7 0 0 0
4 8 0 0 0 
4 7 8 0 1 
*/

Compilation message (stderr)

sequence.cpp: In function 'long long int dfs(std::vector<long long int>, long long int)':
sequence.cpp:35:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i= 0  ; i < vj.size() ; i++){
      |                     ~~^~~~~~~~~~~
sequence.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int j = 0;  j < vec.size() ; j++){
      |                     ~~^~~~~~~~~~~~

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