Submission #828413

#	Time	Username	Problem	Language	Result	Execution time	Memory
828413		tch1cherin	Sequence (BOI14_sequence)	C++17	34 / 100	197 ms	704 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
bool check(int n, int digit) {
  while (n > 0) {
    if (n % 10 == digit) {
      return true;
    }
    n /= 10;
  }
  return false;
}
 
int64_t num = 0;
vector<int64_t> nums;
int cnt[10], max_d = 0;
 
void gen(int pos = 0) {
  nums.push_back(num);
  for (int d = pos == 0 ? 1 : 0; d < 10; d++) {
    if (cnt[d] == 0 || (max_d > d && d != 0) || (d == 0 && pos != 1)) {
      continue;
    }
    int last_max_d = max_d;
    max_d = max(max_d, d);
    num = num * 10 + d;
    cnt[d]--;
    gen(pos + 1);
    cnt[d]++;
    num /= 10;
    max_d = last_max_d;
  }
}
 
int main() {
  int K;
  cin >> K;
  vector<int> B(K);
  for (int &v : B) {
    cin >> v;
  }
  if (K <= 1000) {
    int MAX_X = 1;
    while (MAX_X < K) {
      MAX_X *= 10;
    }
    vector<int> mask1(MAX_X), mask2(MAX_X);
    for (int i = 0; i < MAX_X; i++) {
      for (int j = 0; j < K; j++) {
        if (!check((i + j) % MAX_X, B[j])) {
          if (i + j < MAX_X) {
            mask1[i] |= 1 << B[j];
          } else {
            mask2[i] |= 1 << B[j];
          }
        }
      }
    }
    fill(cnt, cnt + 10, 1);
    gen();
    vector<int64_t> new_nums;
    for (auto x : nums) {
      new_nums.push_back(x);
      for (int d = 0; d < 10; d++) {
        new_nums.push_back(x * 10 + d);
      }
    }
    nums = new_nums;
    int64_t ans = LLONG_MAX;
    for (int i = 0; i < MAX_X; i++) {
      for (auto x : nums) {
        int m1 = mask1[i], m2 = mask2[i];
        int tmp = x;
        while (tmp > 0) {
          m1 &= ~(1 << (tmp % 10));
          tmp /= 10;
        }
        tmp = x + 1;
        while (tmp > 0) {
          m2 &= ~(1 << (tmp % 10));
          tmp /= 10;
        }
        if (m1 + m2 == 0) {
          ans = min(ans, x * MAX_X + i);
        }
      }
    }
    for (int N = 1; N <= 1000; N++) {
      bool Good = true;
      for (int i = 0; i < K; i++) {
        Good &= check(N + i, B[i]);
      }
      if (Good) {
        cout << N << "\n";
        exit(0);
      }
    }
    cout << ans << "\n";
    exit(0);
  }
  const int MAX_N = 1e7;
  for (int N = 1, j = 1; N < MAX_N; N++) {
    j = max(j, N);
    while (j < MAX_N && check(j, B[0])) {
      j++;
    }
    if (j - N >= K) {
      cout << N << "\n";
      exit(0);
    }
  }
}

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