oj.uz

Submission #824956

# Submission time Handle Problem Language Result Execution time Memory
824956 2023-08-14T12:25:11 Z alex_2008 Lottery (CEOI18_lot) C++14
45 / 100
 73 ms 16204 KB 
#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.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 740 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 740 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 73 ms 16204 KB Output is correct
14 Correct 28 ms 13612 KB Output is correct
15 Correct 29 ms 13544 KB Output is correct
16 Correct 56 ms 15512 KB Output is correct
17 Correct 39 ms 14916 KB Output is correct
18 Correct 39 ms 14924 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 740 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 740 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 73 ms 16204 KB Output is correct
14 Correct 28 ms 13612 KB Output is correct
15 Correct 29 ms 13544 KB Output is correct
16 Correct 56 ms 15512 KB Output is correct
17 Correct 39 ms 14916 KB Output is correct
18 Correct 39 ms 14924 KB Output is correct
19 Runtime error 5 ms 596 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -