oj.uz

Submission #421972

# Submission time Handle Problem Language Result Execution time Memory
421972 2021-06-09T14:19:21 Z rama_pang Sequence (BOI14_sequence) C++17
100 / 100
 98 ms 9548 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;
    bool allZero = true;
    for (int i = 0; i < sz; i++) {
      if (save[depth][i]) {
        allZero = false;
      }
    }
    if (allZero) return lastNonZero ? 0 : 1;
    if (sz == 1) {
      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;
      }
      bool checkEqual = sz == newsz;
      for (int i = 0; i < sz; i++) if (checkEqual) {
        if (save[depth][i] != save[depth + 1][i]) {
          checkEqual = false;
        }
      }
      if (!checkEqual) {
        lint newRes = self(self, newsz, (save[depth][0] & 1) == 0 || st != 0, depth + 1);
        res = min(res, newRes * 10ll + st);
      }
    }
    return res;
  };

  save[0] = S;
  lint ans = Solve(Solve, N, 0, 0);
  assert(ans > 0 && CheckAns(ans));

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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 316 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 9 ms 1228 KB Output is correct
3 Correct 12 ms 1320 KB Output is correct
4 Correct 8 ms 1228 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 5 ms 1032 KB Output is correct
7 Correct 41 ms 6472 KB Output is correct
8 Correct 37 ms 4428 KB Output is correct
9 Correct 58 ms 9300 KB Output is correct
10 Correct 65 ms 9292 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 42 ms 4300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 60 ms 9516 KB Output is correct
12 Correct 98 ms 9476 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 11 ms 1228 KB Output is correct
28 Correct 9 ms 1336 KB Output is correct
29 Correct 6 ms 1320 KB Output is correct
30 Correct 6 ms 1228 KB Output is correct
31 Correct 5 ms 960 KB Output is correct
32 Correct 43 ms 6604 KB Output is correct
33 Correct 37 ms 4468 KB Output is correct
34 Correct 58 ms 9548 KB Output is correct
35 Correct 57 ms 9548 KB Output is correct
36 Correct 66 ms 6896 KB Output is correct
37 Correct 89 ms 9352 KB Output is correct
38 Correct 64 ms 5580 KB Output is correct
39 Correct 95 ms 9536 KB Output is correct
40 Correct 94 ms 9548 KB Output is correct