oj.uz

Submission #920065

# Submission time Handle Problem Language Result Execution time Memory
920065 2024-02-02T03:09:10 Z Jawad_Akbar_JJ Lottery (CEOI18_lot) C++17
20 / 100
 128 ms 740 KB 
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>

using namespace std;
const int N = 10000 + 10;
long long mod[2];
int hsh[N][2];
int a[N];
int dp[N][2];
int d[2];
int ans[N];
int res[N][2];

void calc(int t,int i){
	hsh[i][t] = (1LL * hsh[i-1][t] * d[t] + a[i]) % mod[t];
}

int get(int t,int l,int r){
	int H = 1LL * hsh[l][t] * dp[r - l][t] % mod[t];
	return (hsh[r][t] - H + mod[t]) % mod[t];
}

signed  main(){
	mod[0] = 1e9 + 7;
	mod[1] = 998244353;
	d[0] = 256;
	d[1] = 149;

	dp[0][0] = dp[0][1] = 1;

	for (int i=1;i<N;i++)
		dp[i][0] = 1LL * dp[i-1][0] * d[0] % mod[0];

	for (int i=1;i<N;i++)
		dp[i][1] = 1LL * dp[i-1][1] * d[1] % mod[1];
	
	

	int n,l;
	scanf("%d%d",&n,&l);

	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for (int i=1;i<=n;i++){
		calc(0,i);
		calc(1,i);
	}
	for (int i=0;i + l <= n;i++)
		res[i][0] = get(0,i,i+l);
	for (int i=0;i + l <= n;i++)
		res[i][1] = get(1,i,i+l);

	for (int i=0;i + l <= n;i++){
		for (int j=0;j + l <= n;j++)
			if (res[i][0] == res[j][0] and res[i][1] == res[j][1])
				ans[i+1]++;
	}
	int q;
	scanf("%d",&q);
	scanf("%d",&q);

	for (int i=0;i+l <=n;i++)
		printf("%d ",ans[i+1]-1);
	printf("\n");


}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
lot.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
lot.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
lot.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 704 KB Output is correct
2 Correct 50 ms 600 KB Output is correct
3 Correct 34 ms 600 KB Output is correct
4 Correct 37 ms 604 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Correct 29 ms 736 KB Output is correct
7 Correct 20 ms 600 KB Output is correct
8 Correct 38 ms 708 KB Output is correct
9 Correct 41 ms 740 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 18 ms 600 KB Output is correct
13 Correct 13 ms 600 KB Output is correct
14 Correct 13 ms 604 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 704 KB Output is correct
2 Correct 50 ms 600 KB Output is correct
3 Correct 34 ms 600 KB Output is correct
4 Correct 37 ms 604 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Correct 29 ms 736 KB Output is correct
7 Correct 20 ms 600 KB Output is correct
8 Correct 38 ms 708 KB Output is correct
9 Correct 41 ms 740 KB Output is correct
10 Correct 36 ms 600 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 18 ms 600 KB Output is correct
13 Correct 13 ms 600 KB Output is correct
14 Correct 13 ms 604 KB Output is correct
15 Incorrect 31 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -