oj.uz

Submission #828507

# Submission time Handle Problem Language Result Execution time Memory
828507 2023-08-17T10:37:09 Z tch1cherin Sequence (BOI14_sequence) C++17
9 / 100
 1000 ms 1104 KB 
#include <bits/stdc++.h>
using namespace std;

bool check(int n, int digit, int num_digits = -1) {
  if (num_digits == -1) {
    while (n > 0) {
      if (n % 10 == digit) {
        return true;
      }
      n /= 10;
    }
    return false;
  } else {
    for (int i = 0; i < num_digits; i++) {
      if (n % 10 == digit) {
        return true;
      }
      n /= 10;
    }
    return false;
  }
}

int stupid(int K, vector<int> B) {
  for (int N = 1; N <= 10000; N++) {
    bool Good = true;
    for (int i = 0; i < K; i++) {
      Good &= check(N + i, B[i]);
    }
    if (Good) {
      return N;
    }
  }
  return 0;
}

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 smart(int K, vector<int> B) {
  int MAX_X = 1, digits = 0;
  while (MAX_X < K) {
    MAX_X *= 10;
    digits++;
  }
  for (int N = 1; N <= MAX_X; N++) {
    bool Good = true;
    for (int i = 0; i < K; i++) {
      Good &= check(N + i, B[i]);
    }
    if (Good) {
      return N;
    }
  }
  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], digits)) {
        if (i + j < MAX_X) {
          mask1[i] |= 1 << B[j];
        } else {
          mask2[i] |= 1 << B[j];
        }
      }
    }
  }
  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);
      }
    }
  }
  return ans;
}
 
#define STRESSd

using R = uniform_int_distribution<int>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

void get_input(int& K, vector<int>& B) {
  #ifdef STRESS
    K = R(1, 100)(rng);
    int N = R(1, 10000)(rng);
    B.resize(K);
    for (int i = 0; i < K; i++) {
      int tmp = N + i;
      vector<int> digits;
      while (tmp > 0) {
        digits.push_back(tmp % 10);
        tmp /= 10;
      }
      sort(digits.begin(), digits.end());
      digits.resize(unique(digits.begin(), digits.end()) - digits.begin());
      B[i] = digits[R(0, (int)digits.size() - 1)(rng)];
    }
  #else
    cin >> K;
    B.resize(K);
    for (int &v : B) {
      cin >> v;
    }
  #endif
}

int main() {
  fill(cnt, cnt + 10, 1);
  gen();
  vector<int64_t> new_nums;
  for (auto x : nums) {
    if (x != 0) {
      new_nums.push_back(x);
      for (int d = 0; d < 10; d++) {
        new_nums.push_back(x * 10 + d);
      }
      for (int d = 0; d < 10; d++) {
        new_nums.push_back(x * 100 + d * 10 + 9);
      }
    }
  }
  nums = new_nums;
  #ifdef STRESS
    int test = 0;
    while (true) {
      int K;
      vector<int> B;
      get_input(K, B);
      if (smart(K, B) != stupid(K, B)) {
        cout << "WA" << test++ << "\n";
        cout << K << "\n";
        for (int i = 0; i < K; i++) {
          cout << B[i] << " \n"[i + 1 == K];
        }
        exit(0);
      }
      cout << "OK" << test++ << "\n";
    }
  #else
    int K;
    vector<int> B;
    get_input(K, B);
    // cout << stupid(K, B) << "\n";
    cout << smart(K, B) << "\n";
  #endif
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 32 ms 720 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 33 ms 720 KB Output is correct
8 Correct 4 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct
13 Correct 1 ms 720 KB Output is correct
14 Correct 7 ms 720 KB Output is correct
15 Correct 7 ms 720 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 33 ms 780 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 345 ms 756 KB Output is correct
8 Correct 33 ms 720 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Incorrect 327 ms 768 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Execution timed out 1081 ms 720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 720 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 32 ms 720 KB Output is correct
5 Execution timed out 1086 ms 1104 KB Time limit exceeded
6 Halted 0 ms 0 KB -