Submission #622281

#	Time	Username	Problem	Language	Result	Execution time	Memory
622281		jophyyjh	Lottery (CEOI18_lot)	C++14	65 / 100	78 ms	21376 KiB

lot

/**
 * Notes during contest.
 * 
 * ------ A ------
 * Looks like a dp.
 * 
 * ------ 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).
 * 
 * Time Complexity 1: O()
 * Time Complexity 2: O(n * log(n))
 * Time Complexity 3: O(n^2 + q) ([S1-2]), O(n)    (non-deterministic hashing)
 * Implementation 1         (Just for partials, [S1-2], [S3]. [S3] not finished)
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int>    vec;
 
const int INF = 0x3f3f3f3f;
 
int_t pow(int_t a, int_t b, int_t mod) {
    int_t res = 1;
    while (b > 0) {
        if (b % 2 == 1)
            res = res * a % mod;
        a = a * a % mod, b /= 2;
    }
    return res;
}
 
struct RH {     // rolling hash
    std::vector<std::vector<int_t>> _p;
    std::vector<std::vector<int_t>> hash;
    RH(std::vector<std::vector<int_t>> params, const vec& values) {
        int sets = params.size(), n = values.size();
        hash.assign(sets, std::vector<int_t>(n + 1));
        _p = params;
        for (int i = 0; i < sets; i++) {
            int_t p = params[i][0], m = params[i][1];
            hash[i][0] = 0;
            for (int k = 0; k < n; k++) {
                hash[i][k + 1] = hash[i][k] * m % p + int_t(values[k]) % p;
                hash[i][k + 1] = (hash[i][k + 1] % p + p) % p;
            }
        }
    }
    inline std::vector<int_t> find_hash(int s, int l) {
        std::vector<int_t> ans;
        for (int i = 0; i < int(_p.size()); i++) {
            int_t p = _p[i][0], m = _p[i][1];
            int_t val = hash[i][s + l] - hash[i][s] * pow(m, l, p) % p;
            val = (val % p + p) % p;
            ans.push_back(val);
        }
        return ans;
    }
};
 
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int n, l;
    std::cin >> n >> l;
    vec values(n);
    for (int k = 0; k < n; k++)
        std::cin >> values[k];
        
 
    if (n <= 2000) {
        // Mismatch at i, j add 1 to the dist of (s, s+d)   (d = j-i)
        // 1 <= i-s+1 <= l, so max(i-l+1,0) <= s <= i.
        // Note that (l+1) means invalid.
        std::vector<vec> dist(n, vec(n, l + 1));
        for (int d = 1; d < n; d++) {
            vec diff(n + 1, 0);
            for (int i = 0; i + d < n; i++) {
                int j = i + d;
                if (values[i] != values[j])
                    diff[std::max(i - l + 1, 0)]++, diff[i + 1]--;
            }
            for (int i = 0, prefix = 0; i + d + l <= n; i++) {
                prefix += diff[i];
                dist[i][i + d] = prefix;
            }
        }
        for (int i = 0; i < n; i++) {
            dist[i][i] = l + 1;
            for (int j = i + 1; j < n; j++)
                dist[j][i] = dist[i][j];
        }
        std::vector<vec> pre(n, vec(l + 2, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                pre[i][dist[i][j]]++;
            for (int j = 1; j <= l + 1; j++)
                pre[i][j] += pre[i][j - 1];
        }
        int q;
        std::cin >> q;
        for (int _ = 0; _ < q; _++) {
            int sim;
            std::cin >> sim;
            for (int i = 0; i + l - 1 < n; i++)
                std::cout << pre[i][sim] << ' ';
            std::cout << '\n';
        }
    } else {    // [S3] assumes q=1 and k1=0
        // 3 is a primitive root of 998244353. Idk about 5
        RH hash({{998244353, 3}, {int_t(1e9) + 7, 5}}, values);
        std::map<std::vector<int_t>, int> count;
        for (int i = 0; i + l - 1 < n; i++) {
            std::vector<int_t> h = hash.find_hash(i, l);
            for (int_t a : h)
                std::cerr << a << ' ';
            std::cerr << std::endl;
        }
        for (int i = 0; i + l - 1 < n; i++)
            count[hash.find_hash(i, l)]++;
        for (int i = 0; i + l - 1 < n; i++)
            std::cout << count[hash.find_hash(i, l)] - 1 << ' ';
        std::cout << '\n';
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20