oj.uz

Submission #584687

# Submission time Handle Problem Language Result Execution time Memory
584687 2022-06-27T19:54:08 Z MohammadAghil Sequence (BOI14_sequence) C++17
25 / 100
 137 ms 1428 KB 
#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};
          int cr = d;
          rep(i,0,sz(a)){
               if(a[i]>>cr&1) b.back() |= a[i]^(1<<cr);
               else b.back() |= a[i];
               cr++;
               if(cr == 10) cr = 0, b.pb(0);
          }
          while(sz(b) && !b.back()) b.pop_back();
          // cout << sz(b) << '\n';
          ll res = slv(b, d != 9 || sz(a) > 2)*10 + d;
          if(!res) 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 15 ms 340 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 13 ms 340 KB Output is correct
6 Correct 11 ms 404 KB Output is correct
7 Correct 94 ms 980 KB Output is correct
8 Correct 61 ms 828 KB Output is correct
9 Correct 137 ms 1416 KB Output is correct
10 Correct 131 ms 1428 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -