Submission #421826

#	Time	Username	Problem	Language	Result	Execution time	Memory
421826		rama_pang	Sequence (BOI14_sequence)	C++17	0 / 100	1022 ms	1728 KiB

sequence

#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) {
        // cout << K << ' ' << A[i] << ' ' << i << " br" << endl;;
        return false;
      }
      K += 1;
    }
    return true;
  };

  const lint INF = 1e17;
  const auto Solve = [&](const auto &self, vector<int> S, int lastNonZero, int depth) -> lint {
    if (depth >= 17) return INF;
    if (S.size() == 1) {
      if (S[0] == 0) return lastNonZero ? 0 : 1;
      // cout << "hmm" << S[0] << '\n';
      int b = 0;
      lint res = 0;
      if (S[0] & 1) { // must have 0
        lint opt = 1;
        for (b = 1; b <= 9; b++) {
          if ((S[0] >> b) & 1) {
            opt = b;
            break;
          }
        }
        res = opt * 10;
      }
      for (b++; b <= 9; b++) {
        if ((S[0] >> b) & 1) {
          res = res * 10 + b;
        }
      }
      // cout <<  ' ' << res << '\n';
      return res;
    }
    // for (auto x : S) cout << x << ' '; cout << '\n';
    lint res = INF;
    for (int st = 0; st <= 9; st++) {
      int dig = st;
      vector<int> newS;
      int last = 0;
      for (auto add : S) {
        if ((add >> dig) & 1) add ^= 1 << dig;
        last |= add;
        if (dig == 9) {
          newS.emplace_back(last);
          last = 0;
        }
        dig = (dig + 1) % 10;
      }
      if (dig != 0) {
        newS.emplace_back(last);
      }
      lint newRes = self(self, newS, st != 0, depth + 1);
      // cout<< depth << ' ' <<st << ' ' << newRes << " new res\n";
      res = min(res, newRes * 10ll + st);

    }
    return res;
  };

  lint ans = Solve(Solve, S, 0, 0);
  // cout << ans << endl;
  assert(ans > 0 && CheckAns(ans));

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

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

• Subtask 1: 0 / 9
• Subtask 2: 0 / 33
• Subtask 3: 0 / 25
• Subtask 4: 0 / 33