oj.uz

Submission #828413

# Submission time Handle Problem Language Result Execution time Memory
828413 2023-08-17T09:24:25 Z tch1cherin Sequence (BOI14_sequence) C++17
34 / 100
 197 ms 704 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 <= 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 163 ms 516 KB Output is correct
3 Correct 16 ms 468 KB Output is correct
4 Correct 17 ms 532 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 24 ms 540 KB Output is correct
8 Correct 164 ms 528 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 163 ms 528 KB Output is correct
11 Correct 173 ms 528 KB Output is correct
12 Correct 155 ms 524 KB Output is correct
13 Correct 192 ms 524 KB Output is correct
14 Correct 165 ms 468 KB Output is correct
15 Correct 183 ms 528 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 174 ms 520 KB Output is correct
3 Correct 16 ms 468 KB Output is correct
4 Correct 20 ms 536 KB Output is correct
5 Correct 3 ms 424 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 174 ms 524 KB Output is correct
8 Correct 16 ms 468 KB Output is correct
9 Correct 178 ms 528 KB Output is correct
10 Correct 1 ms 428 KB Output is correct
11 Correct 161 ms 524 KB Output is correct
12 Correct 169 ms 524 KB Output is correct
13 Correct 197 ms 536 KB Output is correct
14 Correct 155 ms 520 KB Output is correct
15 Correct 162 ms 528 KB Output is correct
16 Correct 165 ms 532 KB Output is correct
17 Correct 177 ms 532 KB Output is correct
18 Correct 173 ms 528 KB Output is correct
19 Incorrect 193 ms 520 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 2 ms 340 KB Output is correct
5 Correct 14 ms 340 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 20 ms 584 KB Output is correct
8 Correct 13 ms 488 KB Output is correct
9 Correct 17 ms 704 KB Output is correct
10 Correct 26 ms 684 KB Output is correct

Subtask #4
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 22 ms 468 KB Output is correct
4 Correct 22 ms 468 KB Output is correct
5 Incorrect 7 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -