oj.uz

Submission #622473

# Submission time Handle Problem Language Result Execution time Memory
622473 2022-08-04T10:03:10 Z jophyyjh Lottery (CEOI18_lot) C++14
100 / 100
 1110 ms 8708 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~
 * 
 * PS1  Sadly, CSES didn't let me pass impl2 since the last few testcases TLEd. I
 *      then optimized the condition of my for loops to speed it up. I believe that
 *      on oj.uz impl2 would already be enough~ The slight downside is that the
 *      starting points & endpoing
 * 
 * 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.1           (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));
    // 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 = std::max(-k, 0); i < std::min(n - k, l); i++)
            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 = -k; i < n - (l - 1) - k; i++)
            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 + l < n) {
            // dist_new[i] = dist[i] + (values[k+i+l] != values[k+l])
            //                        - (values[k+i] != values[k])
            for (int i = -(k + l); i < n - l - k; i++)
                dist[i + (n - 1)] += (values[k + i + l] != values[k + l]);
            for (int i = -k; i < n - k; i++)
                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 212 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 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 212 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 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 44 ms 440 KB Output is correct
14 Correct 32 ms 572 KB Output is correct
15 Correct 32 ms 516 KB Output is correct
16 Correct 43 ms 588 KB Output is correct
17 Correct 39 ms 576 KB Output is correct
18 Correct 34 ms 564 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 980 KB Output is correct
2 Correct 960 ms 980 KB Output is correct
3 Correct 1025 ms 980 KB Output is correct
4 Correct 999 ms 984 KB Output is correct
5 Correct 495 ms 996 KB Output is correct
6 Correct 952 ms 980 KB Output is correct
7 Correct 554 ms 996 KB Output is correct
8 Correct 718 ms 992 KB Output is correct
9 Correct 995 ms 992 KB Output is correct
10 Correct 1000 ms 980 KB Output is correct
11 Correct 62 ms 468 KB Output is correct
12 Correct 610 ms 920 KB Output is correct
13 Correct 590 ms 1108 KB Output is correct
14 Correct 598 ms 996 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 980 KB Output is correct
2 Correct 960 ms 980 KB Output is correct
3 Correct 1025 ms 980 KB Output is correct
4 Correct 999 ms 984 KB Output is correct
5 Correct 495 ms 996 KB Output is correct
6 Correct 952 ms 980 KB Output is correct
7 Correct 554 ms 996 KB Output is correct
8 Correct 718 ms 992 KB Output is correct
9 Correct 995 ms 992 KB Output is correct
10 Correct 1000 ms 980 KB Output is correct
11 Correct 62 ms 468 KB Output is correct
12 Correct 610 ms 920 KB Output is correct
13 Correct 590 ms 1108 KB Output is correct
14 Correct 598 ms 996 KB Output is correct
15 Correct 951 ms 980 KB Output is correct
16 Correct 916 ms 980 KB Output is correct
17 Correct 999 ms 980 KB Output is correct
18 Correct 953 ms 984 KB Output is correct
19 Correct 990 ms 988 KB Output is correct
20 Correct 1004 ms 984 KB Output is correct
21 Correct 1026 ms 1100 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 212 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 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 44 ms 440 KB Output is correct
14 Correct 32 ms 572 KB Output is correct
15 Correct 32 ms 516 KB Output is correct
16 Correct 43 ms 588 KB Output is correct
17 Correct 39 ms 576 KB Output is correct
18 Correct 34 ms 564 KB Output is correct
19 Correct 1032 ms 980 KB Output is correct
20 Correct 960 ms 980 KB Output is correct
21 Correct 1025 ms 980 KB Output is correct
22 Correct 999 ms 984 KB Output is correct
23 Correct 495 ms 996 KB Output is correct
24 Correct 952 ms 980 KB Output is correct
25 Correct 554 ms 996 KB Output is correct
26 Correct 718 ms 992 KB Output is correct
27 Correct 995 ms 992 KB Output is correct
28 Correct 1000 ms 980 KB Output is correct
29 Correct 62 ms 468 KB Output is correct
30 Correct 610 ms 920 KB Output is correct
31 Correct 590 ms 1108 KB Output is correct
32 Correct 598 ms 996 KB Output is correct
33 Correct 951 ms 980 KB Output is correct
34 Correct 916 ms 980 KB Output is correct
35 Correct 999 ms 980 KB Output is correct
36 Correct 953 ms 984 KB Output is correct
37 Correct 990 ms 988 KB Output is correct
38 Correct 1004 ms 984 KB Output is correct
39 Correct 1026 ms 1100 KB Output is correct
40 Correct 988 ms 2368 KB Output is correct
41 Correct 187 ms 1640 KB Output is correct
42 Correct 1002 ms 2316 KB Output is correct
43 Correct 983 ms 1992 KB Output is correct
44 Correct 972 ms 2120 KB Output is correct
45 Correct 1105 ms 8576 KB Output is correct
46 Correct 209 ms 5000 KB Output is correct
47 Correct 1110 ms 8708 KB Output is correct
48 Correct 1108 ms 6788 KB Output is correct
49 Correct 1088 ms 7464 KB Output is correct