oj.uz

답안 #656448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656448 2022-11-07T13:57:12 Z 600Mihnea 수열 (BOI14_sequence) C++17
100 / 100
 316 ms 1436 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

/**

fix the last digit of our number

**/

const ll INF = (ll) 1e18 + 7;

vector<int> guy, guy2, guy3;
int cnt;

ll solve(vector<int> restrictions, int suf_9, bool only_0) {
  int n = (int) restrictions.size();
  /// if all have 0 restrictions => return 0
  bool all_0 = 1;
  for (auto &x : restrictions) {
    all_0 &= (x == 0);
  }
  if (all_0) {
    return 0;
  }
  if (n == 2 && restrictions[0] == 0) {
    assert(restrictions[1] >= 1);
    /// our number needs to have some digits
    if (restrictions[1] == (1 << 0)) {
      /// our number needs to have only the digit 0
      return 10 - 1; /// special case because it can't start with 0
    }
    ll sol = 0;
    for (int d = 1; d <= 9; d++) {
      if (restrictions[1] & (1 << d)) {
        restrictions[1] ^= (1 << d);
        sol = 10 * sol + d;
        break;
      }
    }
    if (restrictions[1] & (1 << 0)) {
      sol = 10 * sol + 0;
      restrictions[1] ^= (1 << 0);
    }
    for (int d = 1; d <= 9; d++) {
      if (restrictions[1] & (1 << d)) {
        restrictions[1] ^= (1 << d);
        sol = 10 * sol + d;
      }
    }
    assert(restrictions[1] == 0);
    assert(sol - 1 >= 0);
    return sol - 1;
  }
  assert(n >= 1);
  ///cout << "\t\t\t\t\tn = " << n << "\n";
  if (n == 1) {
    if (restrictions[0] == 0) {
      return 1;
    ///  return 1;
      if (!only_0) {
        return 1;
      } else {
        return 0;
      }
    }
    /// our number needs to have some digits
    if (restrictions[0] == (1 << 0)) {
      /// our number needs to have only the digit 0
      return 10; /// special case because it can't start with 0
    }
    ll sol = 0;
    for (int d = 1; d <= 9; d++) {
      if (restrictions[0] & (1 << d)) {
        restrictions[0] ^= (1 << d);
        sol = 10 * sol + d;
        break;
      }
    }
    if (restrictions[0] & (1 << 0)) {
      sol = 10 * sol + 0;
      restrictions[0] ^= (1 << 0);
    }
    for (int d = 1; d <= 9; d++) {
      if (restrictions[0] & (1 << d)) {
        restrictions[0] ^= (1 << d);
        sol = 10 * sol + d;
      }
    }
    assert(restrictions[0] == 0);
    return sol;
  }
  assert(n >= 2);
  ll sol = INF;
  /// T(N) = 10 * T(N / 10) + N => N * log(N) from master theorem (I don't know if log2(N)) or log10(N) but I assume it
  /// is more likely to be log10(N), but nevertheless it intuitively makes sense why it's fast.
  for (int last_digit = 0; last_digit <= 9; last_digit++) {
    vector<int> new_restrictions((last_digit + n - 1) / 10 + 1, 0);
    vector<int> nor((last_digit + n - 1) / 10 + 1, 0);
    for (int i = 0; i < n; i++) {
      int what_digit = (last_digit + i) % 10;
      int val = restrictions[i];
      nor[(last_digit + i) / 10] |= val;
      if (val & (1 << what_digit)) {
        val -= (1 << what_digit);
      }
      new_restrictions[(last_digit + i) / 10] |= val;
      /// (last_digit + i) / 10
    }
    if ((int)restrictions.size() == 2 && (int) new_restrictions.size() == 2 && last_digit == 9 && suf_9 >= 2) {
      continue;
    }
    if ((int) restrictions.size() == 1000 && last_digit == 9) {
      guy = new_restrictions;
      cnt++;
    }
    if (restrictions == guy && last_digit == 9) {
      guy2 = new_restrictions;
    }
    if (restrictions == guy2 && last_digit == 9) {
      guy3 = new_restrictions;
    }
    ll x = solve(new_restrictions, (suf_9 + 1) * (last_digit == 9 && (int) new_restrictions.size() == (int) restrictions.size()), only_0 | (last_digit > 0));
    if (x == 0 && last_digit == 0 && (nor[0] & (1 << 0))) {
      x = 1;
    }
    /**if (restrictions == vector<int> {1 << 0, 1 << 1} && last_digit == 0) {
     /// assert((int) new_restrictions.size() == 2);
      cout << "last_digit = " << last_digit << "\n";
      for (int i = 0; i < (int) new_restrictions.size(); i++) {
        cout << i << " : ";
        for (int dig = 0; dig <= 9; dig++) {
          if (new_restrictions[i] & (1 << dig)) {
            cout << dig << " ";
          }
        }
        cout << "\n";
      }
    //  cout << new_restrictions[0] << "\n";
    //  cout << " x = " << x << "\n";
    }**/
    sol = min(sol, x * 10 + last_digit);
  }
  return sol;
}

signed main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("___input___.txt", "r", stdin);
  }
  int n;
  cin >> n;
  vector<int> restrictions(n, 0);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    assert(0 <= x && x < 10);
    restrictions[i] |= (1 << x);
  }
 /// restrictions = {(1 << 0), (1 << 1)};
  ll sol = solve(restrictions, 0, 0);
  cout << sol << "\n";
  ///assert(cnt == 1);
  return 0;
}
/**

N has digit d[0]
N + 1 has digit d[1]
...
N + i has digit d[i]
N + (K - 1)
what is the smallest possible value of N?

give just a possible value of N, not the smallest one
N = 12345678900000000 is a valid solution
N + 1 = 12345678900000001
N + 2 = 12345678900000002
...

what are the last log10(N) digits?
N         = -----.-----A
N + k - 1 = -----.-----B
with B = A + k - 1 and A, B have the same number of digits

K = 10
A = 00000004
B = 00000013

N         = CA
N + k - 1 = CB
with B = A + k - 1

fix the digits in C in o(2^10)
and after that we have just some restrictions (because we covered some)

restriction of form N + i has digit d[i]

**/

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:154:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 3 ms 324 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 328 KB Output is correct
15 Correct 3 ms 212 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 3 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 5 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 4 ms 212 KB Output is correct
12 Correct 3 ms 212 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 3 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 2 ms 244 KB Output is correct
20 Correct 3 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 3 ms 324 KB Output is correct
23 Correct 3 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 11 ms 416 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 24 ms 340 KB Output is correct
5 Correct 25 ms 340 KB Output is correct
6 Correct 24 ms 392 KB Output is correct
7 Correct 218 ms 948 KB Output is correct
8 Correct 46 ms 732 KB Output is correct
9 Correct 254 ms 1236 KB Output is correct
10 Correct 316 ms 1232 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 145 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 264 ms 1428 KB Output is correct
12 Correct 212 ms 1424 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 3 ms 328 KB Output is correct
15 Correct 2 ms 212 KB Output is correct
16 Correct 5 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 2 ms 328 KB Output is correct
19 Correct 4 ms 332 KB Output is correct
20 Correct 3 ms 324 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 320 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 212 KB Output is correct
26 Correct 3 ms 332 KB Output is correct
27 Correct 11 ms 336 KB Output is correct
28 Correct 11 ms 340 KB Output is correct
29 Correct 26 ms 340 KB Output is correct
30 Correct 27 ms 340 KB Output is correct
31 Correct 23 ms 340 KB Output is correct
32 Correct 185 ms 1112 KB Output is correct
33 Correct 64 ms 724 KB Output is correct
34 Correct 287 ms 1428 KB Output is correct
35 Correct 269 ms 1352 KB Output is correct
36 Correct 202 ms 1120 KB Output is correct
37 Correct 246 ms 1400 KB Output is correct
38 Correct 153 ms 852 KB Output is correct
39 Correct 242 ms 1424 KB Output is correct
40 Correct 251 ms 1436 KB Output is correct