oj.uz

Submission #421805

# Submission time Handle Problem Language Result Execution time Memory
421805 2021-06-09T12:22:49 Z rama_pang Sequence (BOI14_sequence) C++17
0 / 100
 1000 ms 1228 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> S(N);
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    S[i] = 1 << x;
  }

  const auto Solve = [&](const auto &self, vector<int> S, int haveNonZero, int depth) -> lint {
    if (depth >= 17) return 1e17;
    if (S.empty()) return haveNonZero ? 0 : 1;
    if (S.size() == 1) {
      if (S[0] == 0) {
        return haveNonZero ? 0 : 1;
      }
      int b = 0;
      lint res = 0;
      if (S[0] & 1) { // must have 0
        lint opt = 1;
        for (b = 1; b <= 9; b++) {
          if ((S[0] >> b) & 1) {
            opt = b;
            break;
          }
        }
        res = opt * 10;
      }
      for (b++; b <= 9; b++) {
        if ((S[0] >> b) & 1) {
          res = res * 10 + b;
        }
      }
      return res;
    }

    lint res = 1e17;
    for (int st = 0; st <= 9; st++) {
      int dig = st;
      vector<int> newS;
      int last = 0;
      for (auto add : S) {
        if ((add >> dig) & 1) add ^= 1 << dig;
        last |= add;
        if (dig == 9) {
          newS.emplace_back(last);
          last = 0;
        }
        dig = (dig + 1) % 10;
      }
      if (last != 0) {
        newS.emplace_back(last);
      }
      res = min(res, self(self, newS, haveNonZero || st != 0, depth + 1) * 10 + st);
    }
    return res;
  };

  lint ans = Solve(Solve, S, 0, 0);
  assert(ans > 0);
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Incorrect 12 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 308 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 12 ms 316 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Incorrect 12 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 129 ms 412 KB Output is correct
3 Correct 120 ms 400 KB Output is correct
4 Correct 14 ms 332 KB Output is correct
5 Correct 11 ms 332 KB Output is correct
6 Correct 97 ms 364 KB Output is correct
7 Correct 723 ms 948 KB Output is correct
8 Correct 444 ms 732 KB Output is correct
9 Execution timed out 1032 ms 1228 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 5 ms 312 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 428 ms 716 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 12 ms 320 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Incorrect 12 ms 320 KB Output isn't correct
11 Halted 0 ms 0 KB -