답안 #824956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824956	2023-08-14T12:25:11 Z	alex_2008	Lottery (CEOI18_lot)	C++14	45 / 100	73 ms	16204 KB

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.0 / 25.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-