oj.uz

Submission #828416

# Submission time Handle Problem Language Result Execution time Memory
828416 2023-08-17T09:25:08 Z tch1cherin Sequence (BOI14_sequence) C++17
34 / 100
 212 ms 708 KB 
#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 <= 5000; 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 178 ms 516 KB Output is correct
3 Correct 16 ms 532 KB Output is correct
4 Correct 16 ms 536 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 18 ms 532 KB Output is correct
8 Correct 182 ms 520 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 158 ms 520 KB Output is correct
11 Correct 165 ms 520 KB Output is correct
12 Correct 159 ms 516 KB Output is correct
13 Correct 157 ms 520 KB Output is correct
14 Correct 172 ms 520 KB Output is correct
15 Correct 164 ms 524 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 177 ms 524 KB Output is correct
3 Correct 17 ms 532 KB Output is correct
4 Correct 16 ms 532 KB Output is correct
5 Correct 3 ms 532 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 192 ms 520 KB Output is correct
8 Correct 22 ms 532 KB Output is correct
9 Correct 170 ms 520 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 203 ms 524 KB Output is correct
12 Correct 172 ms 524 KB Output is correct
13 Correct 212 ms 528 KB Output is correct
14 Correct 156 ms 516 KB Output is correct
15 Correct 158 ms 524 KB Output is correct
16 Correct 169 ms 528 KB Output is correct
17 Correct 197 ms 520 KB Output is correct
18 Correct 173 ms 516 KB Output is correct
19 Incorrect 176 ms 516 KB Output isn't correct
20 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 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 11 ms 576 KB Output is correct
8 Correct 13 ms 492 KB Output is correct
9 Correct 16 ms 708 KB Output is correct
10 Correct 18 ms 700 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 Correct 157 ms 524 KB Output is correct
3 Correct 18 ms 524 KB Output is correct
4 Correct 16 ms 532 KB Output is correct
5 Incorrect 7 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -