oj.uz

Submission #421971

# Submission time Handle Problem Language Result Execution time Memory
421971 2021-06-09T14:18:23 Z rama_pang Sequence (BOI14_sequence) C++17
25 / 100
 58 ms 9420 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;
}

Compilation message

sequence.cpp: In instantiation of 'main()::<lambda(const auto:23&, int, int, int)> [with auto:23 = main()::<lambda(const auto:23&, int, int, int)>; lint = long long int]':
sequence.cpp:94:34:   required from here
sequence.cpp:86:60: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   86 |         lint newRes = self(self, newsz, save[depth][0] & 1 == 0 || st != 0, depth + 1);
      |                                                          ~~^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 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 368 KB Output is correct
2 Incorrect 1 ms 332 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 1 ms 204 KB Output is correct
2 Correct 10 ms 1228 KB Output is correct
3 Correct 9 ms 1336 KB Output is correct
4 Correct 7 ms 1340 KB Output is correct
5 Correct 6 ms 1332 KB Output is correct
6 Correct 5 ms 1048 KB Output is correct
7 Correct 52 ms 6604 KB Output is correct
8 Correct 44 ms 4556 KB Output is correct
9 Correct 58 ms 9420 KB Output is correct
10 Correct 58 ms 9408 KB Output is correct

Subtask #4
0 / 33.0

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