oj.uz

Submission #217317

# Submission time Handle Problem Language Result Execution time Memory
217317 2020-03-29T11:57:22 Z dolphingarlic Sequence (BOI14_sequence) C++14
67 / 100
 1000 ms 1144 KB 
/*
Baltic 2014 Sequence
- Let each number K be represented as (X)Y, where X = K / 10 and Y = K % 10
    - Notice that now if we remove the last digit from each number, we have
      (X), (X), ..., (X+1), (X+1), ...
    - i.e. we have contiguous segments with the same prefix
    - We can thus merge them together and solve recursively
- For each number, consider the set of digits that it must contain
    - Initially, this set is simply the given digit for each number
    - If we know the last digit of some number, we can simply remove that digit from the set
    - When we only have 1 number, the answer is simply the smallest non-zero number
      with no leading zeroes we can make from the set
- Our solution is thus simply to brute force over each last digit and solve
  the subproblems recursively
    - There are N/10 subproblems because we group numbers in groups of 10
- Also, to efficiently represent the sets of digits, we use bitmasking since then
  we can just add masks for set unions
- Complexity: O(N log N)
*/

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

ll ans = 1e16, pw[18];

void solve(vector<short> sections, ll curr = 0, int level = 0, bool had_zero = false) {
    if (curr > ans) return;
    int n = sections.size();

    if (n == 1) {
        int mask = sections[0];
        if (!mask) {
            if (!curr || had_zero) curr += pw[level];
        } else if (mask == 1) curr += pw[level + 1];
        else {
            if (mask & 1) {
                int mn = 10;
                for (int i = 9; i; i--) {
                    if (mask & (1 << i)) mn = i;
                }
                for (int i = 9; i; i--) {
                    if ((mask & (1 << i)) && i != mn) curr += i * pw[level++];
                }
                curr += mn * pw[++level];
            } else {
                for (int i = 9; i; i--) {
                    if (mask & (1 << i)) curr += i * pw[level++];
                }
            }
        }
        ans = min(ans, curr);
        return;
    }

    FOR(i, 0, 10) {
        vector<short> merged;
        int ins = 0;
        bool zero = false;

        int piv = i;
        FOR(j, 0, n) {
            zero |= (piv == 0 && (sections[j] & 1));
            ins |= (sections[j] & (~(1 << piv)));
            piv++;
            if (piv == 10) {
                merged.push_back(ins);
                ins = piv = 0;
            }
        }
        if (piv) merged.push_back(ins);

        solve(merged, curr + pw[level] * i, level + 1, zero);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<short> sections(n);
    FOR(i, 0, n) {
        int x;
        cin >> x;
        sections[i] = 1 << x;
    }
    pw[0] = 1;
    FOR(i, 1, 18) pw[i] = 10 * pw[i - 1];

    solve(sections);
    cout << ans;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 12 ms 384 KB Output is correct
12 Correct 9 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 15 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 15 ms 384 KB Output is correct
23 Correct 15 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 28 ms 384 KB Output is correct
3 Correct 28 ms 384 KB Output is correct
4 Correct 26 ms 384 KB Output is correct
5 Correct 36 ms 384 KB Output is correct
6 Correct 14 ms 384 KB Output is correct
7 Correct 93 ms 768 KB Output is correct
8 Correct 78 ms 640 KB Output is correct
9 Correct 127 ms 1016 KB Output is correct
10 Correct 126 ms 1024 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 199 ms 632 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 225 ms 1144 KB Output is correct
12 Correct 126 ms 1024 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 12 ms 384 KB Output is correct
15 Correct 9 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 7 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 16 ms 384 KB Output is correct
24 Correct 7 ms 384 KB Output is correct
25 Correct 15 ms 384 KB Output is correct
26 Correct 15 ms 384 KB Output is correct
27 Correct 27 ms 384 KB Output is correct
28 Correct 27 ms 384 KB Output is correct
29 Correct 26 ms 384 KB Output is correct
30 Correct 36 ms 384 KB Output is correct
31 Correct 16 ms 440 KB Output is correct
32 Correct 93 ms 768 KB Output is correct
33 Correct 64 ms 640 KB Output is correct
34 Correct 133 ms 1024 KB Output is correct
35 Correct 135 ms 1144 KB Output is correct
36 Correct 557 ms 768 KB Output is correct
37 Correct 642 ms 1144 KB Output is correct
38 Correct 631 ms 640 KB Output is correct
39 Execution timed out 1063 ms 1144 KB Time limit exceeded
40 Halted 0 ms 0 KB -