oj.uz

답안 #167830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167830 2019-12-10T10:00:03 Z kostia244 Lottery (CEOI18_lot) C++17
45 / 100
 139 ms 33144 KB 
#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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1244 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 7 ms 2808 KB Output is correct
12 Correct 7 ms 2808 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1244 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 7 ms 2808 KB Output is correct
12 Correct 7 ms 2808 KB Output is correct
13 Correct 55 ms 16372 KB Output is correct
14 Correct 96 ms 16376 KB Output is correct
15 Correct 73 ms 16376 KB Output is correct
16 Correct 139 ms 16428 KB Output is correct
17 Correct 124 ms 16504 KB Output is correct
18 Correct 125 ms 16324 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 74 ms 33144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 74 ms 33144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1244 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 7 ms 2808 KB Output is correct
12 Correct 7 ms 2808 KB Output is correct
13 Correct 55 ms 16372 KB Output is correct
14 Correct 96 ms 16376 KB Output is correct
15 Correct 73 ms 16376 KB Output is correct
16 Correct 139 ms 16428 KB Output is correct
17 Correct 124 ms 16504 KB Output is correct
18 Correct 125 ms 16324 KB Output is correct
19 Runtime error 74 ms 33144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -