oj.uz

Submission #617184

# Submission time Handle Problem Language Result Execution time Memory
617184 2022-08-01T09:25:26 Z yutabi Lottery (CEOI18_lot) C++14
20 / 100
 6 ms 1236 KB 
#include <bits/stdc++.h>
using namespace std;


#define MOD 1000000007
#define pb push_back


typedef long long ll;


int n;

int length;


vector <int> s;


vector <vector <int> > k;

vector <int> u;

int ans;

int q;


map <ll,int> mp;


ll pw;


int main()
{
	scanf("%d %d",&n,&length);

	pw=1;

	for(int i=0;i<length-1;i++)
	{
		pw*=46853;
		pw%=MOD;
	}

	s.resize(n);
	k=vector <vector <int> > (n);
	u=vector <int> (n,0);

	for(int i=0;i<n;i++)
	{
		scanf(" %d",&s[i]);
	}

	/*for(int i=0;i<n;i++)
	{
		int l=s[i];

		for(int j=0;j<n;j++)
		{
			if(i==j)
			{
				continue;
			}

			if(min(i,j)+n-max(i,j)<length)
			{
				continue;
			}

			if(s[i]==s[j])
			{
				k[i].pb(n+j-i);
			}
		}
	}*/

	//printf("\n%d\n\n",k[0][0]);

	scanf("	%d",&q);

	int asdasd;

	for(int i=0;i<q;i++)
	{
		scanf(" %d",&asdasd);
	}

	ll hash=0;

	for(int i=0;i<length-1;i++)
	{
		hash*=46853;
		hash%=MOD;

		ll temp=s[i];
		temp*=2147867;
		temp%=MOD;
		temp+=843469;
		temp%=MOD;

		hash+=temp;
		hash%=MOD;
	}

	vector <ll> hashes;

	for(int i=length-1;i<n;i++)
	{
		hash*=46853;
		hash%=MOD;

		ll temp=s[i];
		temp*=2147867;
		temp%=MOD;
		temp+=843469;
		temp%=MOD;

		hash+=temp;
		hash%=MOD;

		hashes.pb(hash);

		mp[hash]++;

		temp=s[i-length+1];
		temp*=2147867;
		temp%=MOD;
		temp+=843469;
		temp%=MOD;
		temp*=pw;
		temp%=MOD;

		hash-=temp;
		hash+=MOD;
		hash%=MOD;
	}

	for(int i=0;i<hashes.size();i++)
	{
		printf("%d ",mp[hashes[i]]-1);
	}
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |  for(int i=0;i<hashes.size();i++)
      |              ~^~~~~~~~~~~~~~
lot.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d %d",&n,&length);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
lot.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf(" %d",&s[i]);
      |   ~~~~~^~~~~~~~~~~~~
lot.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf(" %d",&q);
      |  ~~~~~^~~~~~~~~~
lot.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf(" %d",&asdasd);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 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 212 KB Output is correct
2 Incorrect 1 ms 212 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 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 5 ms 1008 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 5 ms 980 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 5 ms 1008 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 5 ms 980 KB Output is correct
15 Incorrect 6 ms 1236 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 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -