제출 #1312142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312142		LucaLucaM	Sequence (BOI14_sequence)	C++20	0 / 100	698 ms	1204 KiB

sequence

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <bitset>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;
const ll INF = 1e17;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  int n;
  std::cin >> n;

  auto check = [&](ll n, std::vector<std::bitset<10>> restr) {
    for (int i = 0; i < (int) restr.size(); i++) {
      std::bitset<10> dig = 0;
      ll x = n + i;
      while (x) {
        dig[x % 10] = true;
        x /= 10;
      }
      for (int d = 0; d < 10; d++) { 
        if (restr[i][d] && !dig[d]) {
          return false;
        }
      }
    }
    return true;
  };

  auto getSmallest = [&](std::bitset<10> need) -> ll {
    int first = 1;
    while (first < 10 && !need[first]) {
      first++;
    }
    if (first == 10) {
      return 0;
    }
    ll ret = first;
    need[first] = 0;
    for (int i = 0; i < 10; i++) {
      if (need[i]) {
        ret = (ll) ret * 10 + i;
      }
    }
    return ret;
  };

  auto solve = [&](auto &&self, std::vector<std::bitset<10>> restr) -> ll {
    if (restr.empty()) {
      return 0;
    } else if ((int) restr.size() == 1) {
      return getSmallest(restr[0]);
    } else if ((int) restr.size() == 2) {
      std::bitset<10> A = restr[0], B = restr[1];
      ll ret = +INF;
      for (int last = 0; last < 10; last++) {
        std::bitset<10> a = A, b = B;
        b[(last + 1) % 10] = false;
        a |= b;
        if (check(getSmallest(a) * 10 + last, {A, B})) {
          ret = std::min(ret, getSmallest(a) * 10 + last);
        }
        if (check(getSmallest(a), {A, B})) {
          ret = std::min(ret, getSmallest(a));
        }
      }
      std::bitset<10> a = A, b = B;
      a |= b;
      if (check(getSmallest(a), {A, B})) {
        ret = std::min(ret, getSmallest(a));
      }
      ll p10 = 1;
      while (p10 - 1 < ret) {
        if (check(p10 - 1, {A, B})) {
          ret = std::min(ret, p10 - 1);
          break;
        }
        p10 *= (ll) 10;
      }
      ret = +INF;
      for (ll n = 0; n < 1000; n++) {
        if (check(n, {A, B})) {
          ret = std::min(ret, n);
        }
      }
      return ret;
    }

    ll ret = +INF;

    for (int y = 0; y < 10; y++) {
      std::vector<std::bitset<10>> newrestr(((int) restr.size() + y - 1) / 10 + 1);
      // (X)y, (X)y+1, (X)y+2, ..., (X)9
      for (int i = 0; i < (int) restr.size(); i++) {
        int X = (i + y) / 10;
        int marked = (i + y) % 10;
        std::bitset<10> me = restr[i];
        me[marked] = 0;
        newrestr[X] |= me;
      }
      ret = std::min(ret, self(self, newrestr) * 10 + y);
    }

    return ret;
  };
  
  std::vector<std::bitset<10>> a(n);
  for (int i = 0; i < n; i++) {
    int x;
    std::cin >> x;
    a[i] = 0;
    a[i][x] = true;
  }

  std::cout << solve(solve, a);
  
  return 0;
} 

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