oj.uz

Submission #622472

# Submission time Handle Problem Language Result Execution time Memory
622472 2022-08-04T10:02:19 Z jophyyjh Lottery (CEOI18_lot) C++14
100 / 100
 1245 ms 8732 KB 
/**
 * Notes during contest.
 * 
 * ------ A ------
 * Looks like a dp, and the score distribution is interesting too.. Sort the machines
 * and orders by their clock speed. By greedy arguments, if we've seletected the
 * subset of orders & machines, we sort the clock speed in order and assign them.
 * [S3] is the one that gave me the idea: we first sort orders & machines, then use
 * O(nm) dp on prefixes. Note that cores can be shared across orders, so we need an
 * additional val in our dp state, which is the num of cores left. This val can at
 * most be 50. Note that one should take a close look at the memory limit too: our dp
 * sequence shouldn't take up too much memory.
 * 
 * P.S. When about 1.5 hours were left, I left home. Technically I didn't finish the
 *      virtual contest.
 * 
 * ------ B ------
 * I think i've seen sth similar on luogu. First, let's assume that d >= 0 and i'll
 * use the words "increase" & "decrease". If we wanna increase an interval by d, we
 * can greedily increase a suffix (instead of just an interval in the middle). If we
 * are to decrease an interval by d, we can greedily decrease a prefix. The two cases
 * are symmetric, so we can assume that one always increase a suffix by 0 <= d <= x.
 * And, if we're increasing a suffix, why don't we just do d=x? The rest is quite
 * straight-forward.
 * 
 * ------ C ------
 * For k_j = 0, we have to find the num of times each interval appeared. This can be
 * effectively done with str hashing. [S3] solved. [S1] is just brute-force: we can
 * do a O(n^2) for loop, iterating over all pairs of starting pos, naively comparing
 * the dist. of 2 substr. [S2] is a O(n^2) comparison between pairs of VALUES and
 * apply a difference array.
 * We're only looking for the num of mismatches. Let's compress the values (a_i:
 * 10^9 -> 10^4).
 * [After contest]
 * I was so shocked after reading the solution. (Most people thought it was the
 * easiest problem, yet it was the only problem on the 1st day that i couldn't finish
 * myself!) Anyway, let dist[i][j] = dist. between the substr starting at i and the
 * one starting at j. It turns out that a O(n^2) (time comp.) solution can pass! But
 * we must optimize memory usage (O(n^2) memory is too much). The key is to not store
 * dist[][].
 * I computed dist[i][j] by iterating through j-i (from small to large). One may find
 * that a lot of comparisons can be removed, e.g. we have:
 *                  dist[i+1][j+1] = dist[i][j] + (sth) - (sth).
 * Each time, a row of dist[][] is maintained, so we can answer all queries related
 * to that pos. The impl looks kinda neat too~
 * 
 * Time Complexity 1: O(nm * c_max + n * log(n) + m * log(m))
 * Time Complexity 2: O(n * log(n))
 * Time Complexity 3: O(n^2 + qn)
 * Mem. Compleixty 3: O(nq)
 * Implementation 2             (Full solution, memory optimized)
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int>    vec;
 
const int INF = 0x3f3f3f3f;
 
 
struct query_t {
    int q, original_idx;
};
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int n, l, q;
    std::cin >> n >> l;
    vec values(n);
    for (int_t k = 0; k < n; k++)
        std::cin >> values[k];
    std::cin >> q;
    vec queries(q);
    for (int_t i = 0; i < q; i++)
        std::cin >> queries[i];
 
 
    std::vector<vec> ans(n, vec(q, -1));
    // Some 0s in dist[] isn't valid. This is because they don't repr real substrs.
    // But anyway, they may become "real" with other pos k, so we keep those as 
    // "partial comparisons".
    vec dist(2 * n - 1, 0);
    // compare substr starting at 0 at 0+k, skip out of bound positions.
    for (int k = -n + 1; k <= n - 1; k++) {
        for (int i = 0; i < l; i++) {
            if (0 <= i + k && i + k < n)
                dist[k + (n - 1)] += (values[i] != values[i + k]);
        }
    }
    for (int k = 0; k + l <= n; k++) {
        // ans query for pos k
        vec prefix_sum(l + 1, 0);
        for (int i = -n + 1; i <= n - 1; i++) {
            if (0 <= i + k && i + k + (l - 1) < n)
                prefix_sum[dist[i + (n - 1)]]++;
        }
        for (int t = 1; t <= l; t++)
            prefix_sum[t] += prefix_sum[t - 1];
        for (int i = 0; i < q; i++)
            ans[k][i] = prefix_sum[queries[i]] - 1;
        // re-calculate dist[] for the next k
        if (k != n - 1) {
            for (int i = -n + 1; i <= n - 1; i++) {
                // dist_new[i] = dist[i] + (values[k+i+l] != values[k+l])
                //                        - (values[k+i] != values[k])
                if (0 <= k + l && k + l < n && 0 <= k + i + l && k + i + l < n)
                    dist[i + (n - 1)] += (values[k + i + l] != values[k + l]);
                if (0 <= k + i && k + i < n)
                    dist[i + (n - 1)] -= (values[k + i] != values[k]);
            }
        }
    }
    for (int i = 0; i < q; i++) {
        for (int j = 0; j + l <= n; j++)
            std::cout << ans[j][i] << ' ';
        std::cout << '\n';
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 50 ms 440 KB Output is correct
14 Correct 40 ms 588 KB Output is correct
15 Correct 39 ms 520 KB Output is correct
16 Correct 46 ms 596 KB Output is correct
17 Correct 44 ms 588 KB Output is correct
18 Correct 44 ms 596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1194 ms 1000 KB Output is correct
2 Correct 1171 ms 996 KB Output is correct
3 Correct 1175 ms 1000 KB Output is correct
4 Correct 1144 ms 1076 KB Output is correct
5 Correct 775 ms 1092 KB Output is correct
6 Correct 1111 ms 1080 KB Output is correct
7 Correct 782 ms 1104 KB Output is correct
8 Correct 945 ms 1096 KB Output is correct
9 Correct 1141 ms 1080 KB Output is correct
10 Correct 1164 ms 1096 KB Output is correct
11 Correct 81 ms 532 KB Output is correct
12 Correct 798 ms 1012 KB Output is correct
13 Correct 829 ms 1204 KB Output is correct
14 Correct 831 ms 1216 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1194 ms 1000 KB Output is correct
2 Correct 1171 ms 996 KB Output is correct
3 Correct 1175 ms 1000 KB Output is correct
4 Correct 1144 ms 1076 KB Output is correct
5 Correct 775 ms 1092 KB Output is correct
6 Correct 1111 ms 1080 KB Output is correct
7 Correct 782 ms 1104 KB Output is correct
8 Correct 945 ms 1096 KB Output is correct
9 Correct 1141 ms 1080 KB Output is correct
10 Correct 1164 ms 1096 KB Output is correct
11 Correct 81 ms 532 KB Output is correct
12 Correct 798 ms 1012 KB Output is correct
13 Correct 829 ms 1204 KB Output is correct
14 Correct 831 ms 1216 KB Output is correct
15 Correct 1121 ms 1016 KB Output is correct
16 Correct 1090 ms 1084 KB Output is correct
17 Correct 1163 ms 1080 KB Output is correct
18 Correct 1177 ms 1108 KB Output is correct
19 Correct 1134 ms 1084 KB Output is correct
20 Correct 1151 ms 1088 KB Output is correct
21 Correct 1149 ms 1084 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 50 ms 440 KB Output is correct
14 Correct 40 ms 588 KB Output is correct
15 Correct 39 ms 520 KB Output is correct
16 Correct 46 ms 596 KB Output is correct
17 Correct 44 ms 588 KB Output is correct
18 Correct 44 ms 596 KB Output is correct
19 Correct 1194 ms 1000 KB Output is correct
20 Correct 1171 ms 996 KB Output is correct
21 Correct 1175 ms 1000 KB Output is correct
22 Correct 1144 ms 1076 KB Output is correct
23 Correct 775 ms 1092 KB Output is correct
24 Correct 1111 ms 1080 KB Output is correct
25 Correct 782 ms 1104 KB Output is correct
26 Correct 945 ms 1096 KB Output is correct
27 Correct 1141 ms 1080 KB Output is correct
28 Correct 1164 ms 1096 KB Output is correct
29 Correct 81 ms 532 KB Output is correct
30 Correct 798 ms 1012 KB Output is correct
31 Correct 829 ms 1204 KB Output is correct
32 Correct 831 ms 1216 KB Output is correct
33 Correct 1121 ms 1016 KB Output is correct
34 Correct 1090 ms 1084 KB Output is correct
35 Correct 1163 ms 1080 KB Output is correct
36 Correct 1177 ms 1108 KB Output is correct
37 Correct 1134 ms 1084 KB Output is correct
38 Correct 1151 ms 1088 KB Output is correct
39 Correct 1149 ms 1084 KB Output is correct
40 Correct 1177 ms 2404 KB Output is correct
41 Correct 499 ms 1704 KB Output is correct
42 Correct 1156 ms 2408 KB Output is correct
43 Correct 1127 ms 2108 KB Output is correct
44 Correct 1152 ms 2248 KB Output is correct
45 Correct 1237 ms 8596 KB Output is correct
46 Correct 489 ms 5132 KB Output is correct
47 Correct 1245 ms 8732 KB Output is correct
48 Correct 1180 ms 6896 KB Output is correct
49 Correct 1162 ms 7532 KB Output is correct