oj.uz

Submission #843262

# Submission time Handle Problem Language Result Execution time Memory
843262 2023-09-03T20:51:56 Z manizare Sequence (BOI14_sequence) C++14
0 / 100
 190 ms 1492 KB 
#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 = 1){
 
  if(vec.size() == 1){
    int s = vec.back() ;
    //cout << "hi " << s << " " ;
    vector <int> vj ;  
    for(int i = 0 ;i < 10 ; i++){
      if(s>>i&1){
        vj.pb(i) ;
      }
    }
   // cout<< vj.size() << " " ;
    if(vj.size() >= 2){
      if(vj[0] == 0){
        swap(vj[0] , vj[1]) ;
      }
    }else{
      if(vj.size() == 0){
      //  cout << ok << "---\n" ;
        return ok ;
      }
      if(ok && vec[0] == 0){
     //   cout << 1 << "=\n" ; 
        return 1 ;
      } 
      if(vec[0] == 1){
   //     cout << 10 << "_-\n";
        return 10; 
      }
    }
    int ans= 0 ;
    for(int i = 0 ; i < vj.size() ; i++){
      ans *= 10;
      ans += vj[i] ;
    }
  //  cout << ans << " d\n";
    return ans ;
  }
  int ans = inf ; 
  for(int i = 0 ; i < 10 ; i++){
    int k = i , t = 0 ;
    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(vec == vec2 && ok == (i==0)){
      continue ;
    }
    if(i!=0 || (i== 0 && ok == 0)){
      bool ok2 = 1 ;
      for(int i = 0 ; i < vec2.size() ; i++){
        if(vec2[i] != 0 )ok2 =0 ;
      }
      if(ok2 == 1){
        ans = min(ans , i) ;
        continue ;
      }
    }
    ans = min(ans , dfs(vec2 , (i == 0)) * 10 + i) ;
  }
  /*
  for(int i =0 ; i < vec.size() ; i++){
    cout << vec[i] << " " ;
  }
  cout << " - " << ok << " " << ans  << "\n" ;
  */
  return ans ;
}
 
signed main(){
  ios::sync_with_stdio(false); cin.tie(0) ;  
  a10[0] = 1;
  for(int i =1 ;i <= 17 ; i++){
    a10[i] = a10[i-1] * 10 ;
  }
  vector <int> vec;
 // vec.pb(0) ; vec.pb(2) ;
  int n ;cin >> n ;
  for(int i = 1; i <= n; i++){
    int x;
    cin >> x ;
    vec.pb((1<<x)) ;
  } 
   cout << dfs(vec , 1 ) ;
}
/*
  

*/

Compilation message

sequence.cpp: In function 'long long int dfs(std::vector<long long int>, long long int)':
sequence.cpp:47: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]
   47 |     for(int i = 0 ; i < vj.size() ; i++){
      |                     ~~^~~~~~~~~~~
sequence.cpp:58:22: 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]
   58 |     for(int j = 0 ;j < vec.size() ; j++){
      |                    ~~^~~~~~~~~~~~
sequence.cpp:79:25: 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]
   79 |       for(int i = 0 ; i < vec2.size() ; i++){
      |                       ~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 17 ms 600 KB Output is correct
3 Correct 17 ms 600 KB Output is correct
4 Incorrect 16 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 190 ms 1492 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -