제출 #167830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167830		kostia244	Lottery (CEOI18_lot)	C++17	45 / 100	139 ms	33144 KiB

lot

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
short cmp[2020][2020], dp[2020][2020];
int n, l, q;
vi a;
const int mod = 1e9 + 9;
const int base = 11000 + rng()%10000;
ll pw[10100];
map<int, int> hsh;
void solve2() {
	ll hash = 0;
	for(int i = 0; i < n; i++) {
		hash = (hash*base + a[i])%mod;
		if(i-l>=0) {
			hash = hash-(pw[l]*a[i-l])%mod;
			if(hash<0) hash+=mod;
		}
		if(i-l+1>=0)
			hsh[hash]++;
	}
	hash = 0;
	for(int i = 0; i < n; i++) {
		hash = (hash*base + a[i])%mod;
		if(i-l>=0) {
			hash = hash-(pw[l]*a[i-l])%mod;
			if(hash<0) hash+=mod;
		}
		if(i-l+1>=0)
			cout << hsh[hash]-1 << " ";
	}
	exit(0);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pw[0] = 1;
	for(int i = 1; i < 10100; i++)
		pw[i] = (pw[i-1]*1ll*base)%mod;
	cin >> n >> l;
	a.resize(n);
	for(auto &i : a)cin >> i;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			dp[i][j] = a[i]!=a[j];
	int cmped = 0;
	for(int k = 0; (1<<k) <= l; k++) {
		if((1<<k)&l) {
			for(int i = 0; i < n; i++) {
				for(int j = i+1; j < n; j++) {
					cmp[i][j] += dp[i+cmped][j+cmped];
				}
			}
			cmped += (1<<k);
		}
		for(int i = 0; i+(1<<k) < n; i++) {
			for(int j = i+1; j+(1<<k) < n; j++) {
				dp[i][j] += dp[i+(1<<k)][j+(1<<k)];
			}
		}
	}
	int q, z;
	cin >> q;
	int ans[10010];
	while(q--) {
		cin >> z;
		if(q==0&&z==0) solve2();
		memset(ans, 0, sizeof ans);
		for(int i = 0; i+l-1 < n; i++) {
			for(int j = i+1; j+l-1 < n; j++)
				ans[i] += cmp[i][j]<=z, ans[j]+=cmp[i][j]<=z;
			cout << ans[i] << ' ';
		}
		cout << '\n';
	}
}

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