Submission #824956

#	Time	Username	Problem	Language	Result	Execution time	Memory
824956		alex_2008	Lottery (CEOI18_lot)	C++14	45 / 100	73 ms	16204 KiB

lot

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e3 + 10;
ll hashes[N];
ll P = 1e9 + 7, Q = 1403072387;
ll binpow(ll a, ll x) {
	if (x == 0) return 1;
	if (x % 2 == 0) {
		ll u = binpow(a, x / 2);
		return (u * u) % Q;
	}
	return (a * binpow(a, x - 1)) % Q;
}
int a[10010];
short dp[N][N];
vector <short> v[N];
int n, l;
int ans(int left, int right) {
	return dp[left][right] - dp[left + l][right + l];
}
int main() {
	cin >> n >> l;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n <= 2000) {
		for (int i = n; i >= 1; i--) {
			for (int j = i + 1; j <= n; j++) {
				dp[i][j] = dp[i + 1][j + 1] + (a[i] != a[j]);
			}
		}
		for (int i = 1; i <= n - l + 1; i++) {
			for (int j = i - 1; j >= 1; j--) {
				v[i].push_back(ans(j, i));
			}
			for (int j = i + 1; j + l <= n + 1; j++) {
				v[i].push_back(ans(i, j));
			}
			sort(v[i].begin(), v[i].end());
		}
		int q;
		cin >> q;
		while (q--) {
			int x;
			cin >> x;
			for (int i = 1; i <= n - l + 1; i++) {
				cout << upper_bound(v[i].begin(), v[i].end(), x) - v[i].begin() << " ";
			}
			cout << "\n";
		}
		return 0;
	}
	int q;
	cin >> q;
	int val;
	cin >> val;
	ll hash = 0;
	map <ll, int> mp;
	for (int i = 1; i <= l; i++) {
		hash += binpow(P, i) * a[i];
		hash %= Q;
	}
	hashes[1] = hash;
	mp[hash]++;
	for (int i = l + 1; i <= n; i++) {
		ll u = (binpow(P, 1) * a[i - l]) % Q;
		hash = (hash + Q - u) % Q;
		hash = (hash * binpow(P, Q - 2)) % Q;
		hash = (hash + binpow(P, l) * a[i]) % Q;
		hashes[i - l + 1] = hash;
		mp[hash]++;
	}
	for (int i = 1; i <= n - l + 1; i++) {
		cout << mp[hashes[i]] - 1 << " ";
	}
}

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