oj.uz

답안 #824811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
824811 2023-08-14T10:43:32 Z joelgun14 Lottery (CEOI18_lot) C++17
45 / 100
 337 ms 596 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int mod = 1723342759;
int key = 1474064957;
ll mul(ll a, ll b) {
	return (a * b) % mod;
}
int main() {
	// sub 1 -> brute force
	// sub 2 -> ?
	// sub 3 -> hashing
	// sub 4 -> ?
	// sub 5 -> ?
	int n, l;
	cin >> n >> l;
	int a[n + 1];
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	int q;
	cin >> q;
	int query[q + 1];
	for(int i = 1; i <= q; ++i)
		cin >> query[i];
	// for subtask 1, just compute for each l, r pair in O(N)
	if(n <= 300) {
		int diff[n + 1][n + 1];
		memset(diff, -1, sizeof(diff));
		for(int i = 1; i <= n; ++i) {
			for(int r = i + 1; r + l - 1 <= n; ++r) {
				diff[i][r] = 0;
				for(int k = 0; k < l; ++k) {
					if(a[i + k] != a[r + k])
						++diff[i][r];
				}
				//cout << i << " " << r << " " << diff[i][r] << endl;
			}
		}
		for(int i = 1; i <= q; ++i) {
			int res[n + 1];
			memset(res, 0, sizeof(res));
			for(int j = 1; j <= n; ++j) {
				for(int k = j + 1; k <= n; ++k) {
					//cout << diff[j][k] << endl;
					if(diff[j][k] != -1 && diff[j][k] <= query[i])
						++res[j], ++res[k];
				}
			}
			for(int j = 1; j <= n - l + 1; ++j)
				cout << res[j] << " ";
			cout << endl;
		}
	}
	else {
		// buat test case query = 0
		// pakai hashing utk cek sama atau tidak in O(1)
		ll hash[n + 1];
		for(int i = 1; i + l - 1 <= n; ++i) {
			hash[i] = 0;
			for(int j = i; j < i + l; ++j) {
				hash[i] = (mul(key, hash[i]) + a[j]) % mod;
			}
			//cout << hash[i] << " ";
		}
		//cout << endl;
		int res[n + 1];
		memset(res, 0, sizeof(res));
		for(int i = 1; i + l - 1 <= n; ++i) {
			for(int j = 1; j < i; ++j) {
				if(hash[i] == hash[j])
					++res[i], ++res[j];
			}
		}
		for(int i = 1; i + l - 1 <= n; ++i)
			cout << res[i] << " ";
		cout << endl;
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Incorrect 2 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 460 KB Output is correct
2 Correct 42 ms 468 KB Output is correct
3 Correct 33 ms 460 KB Output is correct
4 Correct 59 ms 508 KB Output is correct
5 Correct 336 ms 536 KB Output is correct
6 Correct 115 ms 468 KB Output is correct
7 Correct 337 ms 484 KB Output is correct
8 Correct 290 ms 496 KB Output is correct
9 Correct 76 ms 492 KB Output is correct
10 Correct 69 ms 536 KB Output is correct
11 Correct 30 ms 332 KB Output is correct
12 Correct 203 ms 464 KB Output is correct
13 Correct 328 ms 488 KB Output is correct
14 Correct 327 ms 488 KB Output is correct

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 460 KB Output is correct
2 Correct 42 ms 468 KB Output is correct
3 Correct 33 ms 460 KB Output is correct
4 Correct 59 ms 508 KB Output is correct
5 Correct 336 ms 536 KB Output is correct
6 Correct 115 ms 468 KB Output is correct
7 Correct 337 ms 484 KB Output is correct
8 Correct 290 ms 496 KB Output is correct
9 Correct 76 ms 492 KB Output is correct
10 Correct 69 ms 536 KB Output is correct
11 Correct 30 ms 332 KB Output is correct
12 Correct 203 ms 464 KB Output is correct
13 Correct 328 ms 488 KB Output is correct
14 Correct 327 ms 488 KB Output is correct
15 Incorrect 100 ms 448 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Incorrect 2 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -