제출 #1312097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312097		LucaLucaM	수열 (BOI14_sequence)	C++20	25 / 100	1095 ms	2180 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 solve = [&](auto &&self, std::vector<std::bitset<10>> restr) -> ll {
    if ((int) restr.size() <= 2) {
      ll n = 0;
      while (n < 1000 && !check(n, restr)) {
        n++;
      }
      if (n == 1000) {
        return +INF;
      }
      return n;
    }

    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: 25 / 25
• Subtask 4: 0 / 33