oj.uz

Submission #920061

# Submission time Handle Problem Language Result Execution time Memory
920061 2024-02-02T03:05:23 Z Jawad_Akbar_JJ Lottery (CEOI18_lot) C++17
20 / 100
 1430 ms 1228 KB 
#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:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
lot.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
lot.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
lot.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  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 1430 ms 888 KB Output is correct
2 Correct 1329 ms 872 KB Output is correct
3 Correct 1207 ms 632 KB Output is correct
4 Correct 1233 ms 868 KB Output is correct
5 Correct 326 ms 736 KB Output is correct
6 Correct 1113 ms 848 KB Output is correct
7 Correct 643 ms 708 KB Output is correct
8 Correct 1248 ms 724 KB Output is correct
9 Correct 1266 ms 980 KB Output is correct
10 Correct 1264 ms 980 KB Output is correct
11 Correct 50 ms 552 KB Output is correct
12 Correct 622 ms 696 KB Output is correct
13 Correct 447 ms 600 KB Output is correct
14 Correct 450 ms 1228 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1430 ms 888 KB Output is correct
2 Correct 1329 ms 872 KB Output is correct
3 Correct 1207 ms 632 KB Output is correct
4 Correct 1233 ms 868 KB Output is correct
5 Correct 326 ms 736 KB Output is correct
6 Correct 1113 ms 848 KB Output is correct
7 Correct 643 ms 708 KB Output is correct
8 Correct 1248 ms 724 KB Output is correct
9 Correct 1266 ms 980 KB Output is correct
10 Correct 1264 ms 980 KB Output is correct
11 Correct 50 ms 552 KB Output is correct
12 Correct 622 ms 696 KB Output is correct
13 Correct 447 ms 600 KB Output is correct
14 Correct 450 ms 1228 KB Output is correct
15 Incorrect 1205 ms 1148 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 -