oj.uz

Submission #920062

# Submission time Handle Problem Language Result Execution time Memory
920062 2024-02-02T03:06:37 Z Jawad_Akbar_JJ Lottery (CEOI18_lot) C++17
20 / 100
 1423 ms 1136 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];

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++){
		int f = get(0,i,i + l);
		int s = get(1,i,i + l);
		for (int j=0;j + l <= n;j++)
			if (get(0,j,j+l) == f and get(1,j,j+l) == s)
				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:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
lot.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
lot.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
lot.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 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 1 ms 344 KB Output is correct
2 Incorrect 1 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 1423 ms 896 KB Output is correct
2 Correct 1322 ms 600 KB Output is correct
3 Correct 1203 ms 876 KB Output is correct
4 Correct 1229 ms 848 KB Output is correct
5 Correct 324 ms 600 KB Output is correct
6 Correct 1115 ms 1136 KB Output is correct
7 Correct 642 ms 612 KB Output is correct
8 Correct 1248 ms 880 KB Output is correct
9 Correct 1259 ms 648 KB Output is correct
10 Correct 1268 ms 628 KB Output is correct
11 Correct 50 ms 592 KB Output is correct
12 Correct 620 ms 600 KB Output is correct
13 Correct 448 ms 888 KB Output is correct
14 Correct 449 ms 640 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1423 ms 896 KB Output is correct
2 Correct 1322 ms 600 KB Output is correct
3 Correct 1203 ms 876 KB Output is correct
4 Correct 1229 ms 848 KB Output is correct
5 Correct 324 ms 600 KB Output is correct
6 Correct 1115 ms 1136 KB Output is correct
7 Correct 642 ms 612 KB Output is correct
8 Correct 1248 ms 880 KB Output is correct
9 Correct 1259 ms 648 KB Output is correct
10 Correct 1268 ms 628 KB Output is correct
11 Correct 50 ms 592 KB Output is correct
12 Correct 620 ms 600 KB Output is correct
13 Correct 448 ms 888 KB Output is correct
14 Correct 449 ms 640 KB Output is correct
15 Incorrect 1206 ms 1108 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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