oj.uz

Submission #828451

# Submission time Handle Problem Language Result Execution time Memory
828451 2023-08-17T09:42:39 Z tch1cherin Sequence (BOI14_sequence) C++17
25 / 100
 171 ms 724 KB 
#include <bits/stdc++.h>
using namespace std;
 
bool check(int n, int digit, int num_digits = -1) {
  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], MAX_X)) {
          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 ((i + K) * 10 < MAX_X && x != 0) {
          m1 &= ~1;
        }
        if (((i + K) % MAX_X) * 10 < MAX_X && x != 0) {
          m2 &= ~1; 
        }
        if (m1 + m2 == 0) {
          ans = min(ans, x * MAX_X + i);
        }
      }
    }
    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
0 / 9.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Incorrect 171 ms 520 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 468 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 10 ms 272 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 10 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 11 ms 580 KB Output is correct
8 Correct 13 ms 468 KB Output is correct
9 Correct 22 ms 724 KB Output is correct
10 Correct 19 ms 696 KB Output is correct

Subtask #4
0 / 33.0

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