oj.uz

Submission #421838

# Submission time Handle Problem Language Result Execution time Memory
421838 2021-06-09T12:51:54 Z rama_pang Sequence (BOI14_sequence) C++17
100 / 100
 346 ms 9540 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> S(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    S[i] = 1 << A[i];
  }

  const auto CheckAns = [&](lint K) {
    for (int i = 0; i < N; i++) {
      auto str = to_string(K);
      if (count(begin(str), end(str), '0' + A[i]) == 0) {
        return false;
      }
      K += 1;
    }
    return true;
  };

  const lint INF = 1e17;
  vector<vector<int>> save(20, vector<int>(N));
  const auto Solve = [&](const auto &self, int sz, int lastNonZero, int depth) -> lint {
    if (depth >= 17) return INF;
    if (sz == 0) return lastNonZero ? 0 : 1;
    if (sz == 1) {
      if (save[depth][0] == 0) return lastNonZero ? 0 : 1;
      if (save[depth][0] == 1) return 10;
      int b = 0;
      lint res = 0;
      if (save[depth][0] & 1) { // must have 0
        lint opt = 1;
        for (b = 1; b <= 9; b++) {
          if ((save[depth][0] >> b) & 1) {
            opt = b;
            break;
          }
        }
        res = opt * 10;
      }
      for (b++; b <= 9; b++) {
        if ((save[depth][0] >> b) & 1) {
          res = res * 10 + b;
        }
      }
      return res;
    }
    lint res = INF;
    for (int st = 0; st <= 9; st++) {
      int dig = st;
      int newsz = 0;
      int last = 0;
      for (int id = 0; id < sz; id++) {
        int add = save[depth][id];
        if ((add >> dig) & 1) add ^= 1 << dig;
        last |= add;
        if (dig == 9) {
          save[depth + 1][newsz++] = last;
          last = 0;
        }
        dig = (dig + 1) % 10;
      }
      if (last != 0) {
        save[depth + 1][newsz++] = last;
      }
      lint newRes = self(self, newsz, st != 0, depth + 1);
      res = min(res, newRes * 10ll + st);
    }
    return res;
  };

  save[0] = S;
  lint ans = Solve(Solve, N, 0, 0);

  for (lint i = 1; i <= 1000; i++) {
    if (CheckAns(i)) {
      ans = min(ans, i);
    }
  }

  cout << ans << '\n';
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 4 ms 404 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 6 ms 332 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 4 ms 312 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 4 ms 332 KB Output is correct
13 Correct 5 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 6 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 4 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 4 ms 312 KB Output is correct
23 Correct 4 ms 312 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 37 ms 1228 KB Output is correct
3 Correct 39 ms 1228 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 30 ms 972 KB Output is correct
7 Correct 230 ms 6508 KB Output is correct
8 Correct 144 ms 4428 KB Output is correct
9 Correct 330 ms 9292 KB Output is correct
10 Correct 330 ms 9292 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 145 ms 4172 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 311 ms 9300 KB Output is correct
12 Correct 319 ms 9300 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 3 ms 332 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 4 ms 332 KB Output is correct
20 Correct 4 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 2 ms 204 KB Output is correct
25 Correct 4 ms 332 KB Output is correct
26 Correct 4 ms 332 KB Output is correct
27 Correct 37 ms 1228 KB Output is correct
28 Correct 40 ms 1228 KB Output is correct
29 Correct 6 ms 1228 KB Output is correct
30 Correct 5 ms 1228 KB Output is correct
31 Correct 29 ms 972 KB Output is correct
32 Correct 232 ms 6556 KB Output is correct
33 Correct 146 ms 4428 KB Output is correct
34 Correct 339 ms 9292 KB Output is correct
35 Correct 322 ms 9420 KB Output is correct
36 Correct 240 ms 6988 KB Output is correct
37 Correct 346 ms 9292 KB Output is correct
38 Correct 195 ms 5580 KB Output is correct
39 Correct 338 ms 9540 KB Output is correct
40 Correct 333 ms 9420 KB Output is correct